CPTS553 Assignment 7 Solved

Description

Assignment 7

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

1. Some questions about drawing 𝑄_𝑘 graphs on surfaces. A. Show that 𝑄₃ can be drawn on the plane.
   1. Use the fact that 𝑄₄ is bipartite and a total edge count argument to show that 𝑄₄ cannot be drawn on the plane.
   2. Draw 𝑄₄ on the torus (use the 𝑎𝑏𝑎⁻¹𝑏⁻¹ square representation drawn below). HINT:  𝑄₄ is isomorphic to 𝐶₄ × 𝐶₄.

5. Show that 𝑔(𝑄₅) ≥ 5. Recall that for 𝑄₅ we have 𝑛 = 32 and 𝑚 =
6. 80. As a first step, use a total edge count argument to show that

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

1. (⋆) 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:
3. 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: