Homework Set XII and Problem Set L (4/23)

Do for discussion Mon. 4/26:
Sect. 8.4, # 8.
## L1(a), L2(a).

Do for discussion Wed. 4/28:
## L1(b), L2(b-d), L3.

Problem Set L

Theorem L. If G is a planar graph and has girth g (where 3 <= g < infinity), then q <= [g/(g-2)](p-2).

L1. Use Theorem L to solve:
(a) Find cr(P), P = Petersen graph.
(b) Find cr(H), H = Heawood graph (Fig. 4.2.4).

L2. Use Theorem L to do (a, b, d).
(a) Prove: A cubic graph with girth g = 6 cannot be planar.
(b) Prove: A cubic graph with g >= 6 cannot be planar.
(c) Can a cubic graph with g = 5 be planar?
(d) Find a lower bound on cr(G) when G is cubic and has girth 6.

L3. Prove Theorem L.

L4. Prove that cr(K₆ - edge) >= 2.