Homework Set X (4/5, 8)

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 Tues. 4/12:
Sect. 8.1, ## 1-5, 7, 10.
## J1, J6.

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

Hand in Fri. 4/15:
Sect. 8.1, ## 6, 11.
Sect. 9.1, # 1, 7, 11.
## J2, J4(b, e), J5.
## Aut.6, LG.6.
# I2(b) (postponed from HW IX).

If you didn't already give them to me, HAND IN PROBLEMS
      I2(b), Aut.6, LG.6
by Thurs. 4/28, 5:00, at latest. I will return the graded problems on Friday. (Leave them in my mailbox in the math office or under my door.)

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 χ(G) = 4.
(b) Is G critical?

J2. Find χ'(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.

J6. Compare the lower bound p(g) on the order of a g-cage (Theorem 4.2.A) to the actual order of every known g-cage given in the book. Which cages have order equal to p(g)? Which have order greater than p(g)? What does it mean when a g-cage has order > p(g)?