CS453 Graph Theory Assignment 7

Description

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: