## 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.

Go to announcements | course information | homework list | previous homework | next homework.

## 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_{6} - edge) >= 2.