CS453 - Graph Theory  - Assignment 7 - Solved

1.     Some questions about drawing 𝑄𝑘 graphs on surfaces. A. Show that 𝑄3 can be drawn on the plane.

B.    Use the fact that 𝑄4 is bipartite and a total edge count argument to show that 𝑄4 cannot be drawn on the plane.

C.    Draw 𝑄4 on the torus (use the 𝑎𝑏𝑎−1𝑏−1 square representation drawn below).  HINT:  𝑄4 is isomorphic to 𝐶4 × 𝐶4.

 

 

D.    Show that 𝑔(𝑄5) ≥ 5.  Recall that for 𝑄5 we have 𝑛 = 32 and 𝑚 =

80.  As a first step, use a total edge count argument to show that

𝑟 ≤ 40.  Feed this information into Euler’s formula  𝑛 − 𝑚 + 𝑟 = 2 − 2 𝑔(𝑄5).

E.     (⋆)  Generalize the strategy in part D to obtain a “meaningful” lower bound for 𝑔(𝑄𝑘).  Here, recall that 𝑛 = 2𝑘 and 𝑚 = 𝑘2𝑘−1.

 

           

2.     The Petersen graph 𝑃 is depicted:

 

A. Use a total edge count argument to show that 𝑃 is non-planar.  You may use the fact that 𝑃 has no triangles or 4-cycles as subgraphs. B. Draw 𝑃 on a torus without the edges crossing.

 

 

 

           

3.  Draw 𝐾4,4 on a torus without the edges crossing.  Suggestion:  Start with your two partite sets (every edge joins a red vertex to a blue vertex) arranged as shown.