Homework Set X and Problem Set J (4/1)

Read Sect. 8.1 and Sect. 9.1. The proof of Theorem 9.1.7 is optional. The most interesting thing about the proof of Theorem 9.1.6 is that it uses Turán's Theorem!

Do for discussion Thurs. 4/15:
Sect. 8.1, ## 1-5, 7, 10.
# J1.

Do for discussion Fri. 4/16:
Sect. 8.1, ## 8, 9, 12, 13.
Sect. 9.1, ## 3, 4, 8, 12, 13.
## J3, J4(a, c, d).

Hand in Mon. 4/19:
Sect. 8.1, ## 6, 11.
Sect. 9.1, # 1, 7, 11.
## J2, J4(b, e), J5.

Definitions and Corrections

• In Sect. 9.1, p. 180 and Exercise 9.1.11: Kuratowski's Theorem means the combination of Theorems 9.1.1 and 9.1.2 (although 9.1.1 is relatively easy and is not the part he's famous for).
• In Sect. 9.1, p. 180: A simple drawing must also satisfy
      d) no edge passes through any vertex.

Problem Set J

J1. Let G be the Grötzsch graph (Fig. 2.1.6).
(a) Prove chi(G) = 4.
(b) Is G critical?

J2. Find chi'(Z) where Z is the graph of Fig. 2.3.1.

J3. Show that the graph of Fig. 9.1.16 is nonplanar.

J4. Planar or nonplanar? Prove it!
(a) Fig. 9.1.19.
(b) Fig. 9.1.18.
(c) Fig. 9.1.17.
(d) Fig. 9.2.1, left.
(e) Fig. 9.2.1, right.

J5. Prove that K_3,3 is the unique 4-cage.