Homework Set XIII (5/11)

For Wed.-Fri. 5/11-23: Read Sect. 9.3 (a continuation of splitting number, in the dual graph) and Sect. 10.3, pp. 225-227, pp. 228(bottom)-229, Theorem 10.3.3.

Do for discussion Wed. 5/11:
      # M1.

Do for discussion Fri. 5/13:
Review problems:
      Sect. 9.3, ## 2-5.
      Sect. 10.3, # 1.
New material (graphs in surfaces):
      Sect. 10.3, ## 7, 9.
      # M2, M3 (at your discretion; I tend to prefer M3).

Terminology

• "Embedding" a graph is the technical term for drawing it without crossings or any other self-intersection.
• In Sect. 10.3 they often say "circuit of a rotation". What they mean is a region of an embedding of the graph in a surface. "Rotations" are a technical tool that I will avoid. I'll explain this in class.
• See the announcements page for the Euler formulas for graphs embedded in multiple tori.
• Here are pages with diagrams for T₁ (the torus) and T₂ (the double torus), or both T₁ and T₂, that you can use for drawing graphs.

Problem Set M

Problem M1 is basic. The others are for those who enjoy embedding graphs on surfaces (as I do; it's recreational math).

M1. Try to embed non-planar complete graphs in the torus. Start with K₅ (naturally), and if you succeed, try K₆ and then K₇ and then ....

M2. The same as # M1, for the double torus.
Use theorems in Section 10.3 to decide where to stop embedding in the torus.

M3. Try to embed non-planar complete bipartite graphs in the torus. Start with K_3,3 (naturally), and if you succeed, try K_3,4 and then K_3,5 and K_4,4 – and then (we're getting into summer plans here) ....
Use theorems in Section 10.3 to decide where to stop embedding in the torus.