CS453 Assignment 7 Solved

Questions with a (⋆) are each worth 1 bonus point for 453 students.

1. Some questions about drawing 𝑄𝑘 graphs on surfaces.

1. Show that 𝑄3 can be drawn on the plane.
2. Use the fact that 𝑄4 is bipartite and a total edge count argument to

   show that 𝑄4 cannot be drawn on the plane.

3. Draw 𝑄4 on the torus (use the 𝑎𝑏𝑎−1𝑏−1 square representation

   drawn below). HINT: 𝑄4 is isomorphic to 𝐶4 × 𝐶4.

4. 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).

5. (⋆) 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 𝐾 on a torus without the edges crossing. Suggestion: Start 4,4

with your two partite sets (every edge joins a red vertex to a blue vertex) arranged as shown: