Questions with a (โ) are each worth 1 bonus point for 453 students.
Some questions about drawing ๐๐ graphs on surfaces. A. Show that ๐3 can be drawn on the plane.Use the fact that ๐4 is bipartite and a total edge count argument to show that ๐4 cannot be drawn on the plane.
Draw ๐4 on the torus (use the ๐๐๐−1๐−1 square representation drawn below). HINT: ๐4 is isomorphic to ๐ถ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).
(โ) Generalize the strategy in part D to obtain a “meaningful” lower bound for ๐(๐๐). Here, recall that ๐ = 2๐ and ๐ = ๐2๐−1.
The Petersen graph ๐ is depicted:
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.
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:
