Homework Set XII (5/3, 9, 11)

Read for Wed. 5/4 and Fri. 5/6: Sects. 8.4, 9.2.

Do for discussion Mon. 5/9:
Sect. 8.4, ## 1, 2, 4, 7.
Sect. 9.2, ## 2, 3.
## L2(a), L3(a), L6.

Do for discussion Tues. 5/10:
Sect. 8.4, ## 5, 8, 9.
Sect. 9.2, ## 6, 7.
## L5, L8.

Hand in Wed. 5/11:
Sect. 8.4, ## 3, 6, 11.
Sect. 9.2, # 4.
## L1, L1', L2(b), L3(b-d), L7, L9.
Hint for L1': Study the second proof of Theorem 9.1.4.
NOTE: There are really too many hand-in problems. The more important ones are 9.2.4, L1, L1', L2(b), L3(b), L7.

Definitions and Corrections

• Exercise 8.4.9 should read: Find the smallest graph that is planar and regular of degree 3 and has a plane drawing where every edge has the same geometric length.
• See the announcements page for more.

Problem Set L

We define the girth of a forest (such as a tree) to be infinity. Then the girth of a graph is always ≥ 3.

L1.
(a) Prove Theorem G. If G is a planar graph and has girth ≥ g, and if p ≥ 3, then q ≤ [g/(g-2)](p-2).
(b) [ADDED 5/9] What does this say if g = 3?
(c) [ADDED 5/9] What does this say if G is bipartite?

L1'. [ADDED 5/9]
(a) Prove Theorem CR. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then cr(G) ≥ q - [g/(g-2)](p-2).
(b) What does this say if g = 3?
(c) What does this say if G is bipartite?

L1'' [ADDED 5/11] (This was proved in class, I think. I did prove the case g = 3 in class on 5/6. Feel free to use this theorem if it helps you.)
Theorem SPL. If G is a graph (not necessarily planar) and has girth ≥ g, and if p ≥ 3, then σ(G) ≥ [(g-2]/g] q - (p-2).

L2. Use the theorems to solve:
(a) Find cr(P), P = Petersen graph.
(b) Find cr(H), H = Heawood graph (Fig. 4.2.4).

L3. Use the theorems 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.

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

L5. Find θ(P), where P is the Petersen graph.

L6. Prove that θ(K_n) ≥ ceiling[(n+2)/6] for all n ≥ 1.

L7. Let c(G) = the number of cycles in the graph G.
(a) Prove Theorem M: If c(G) < min(c(K₅), c(K_3,3)), then G is planar. (Hint: Use Kuratowski's theorem.)
(b) Evaluate the minimum in Theorem M.
(c) Use (b) to solve Exercise 8.1.3. (If you didn't solve (b), just prove the minimum in (b) is > 3; that should be enough for Exercise 8.1.3.)

L8. Let H = Heawood graph, Fig. 4.2.4.
(a) Prove σ(H) ≥ 2. (Hint: One way is to use theorems above.)
(b) We know σ(H) ≤ 3. Decide whether σ(H) = 2 or 3.

L9. Prove σ(P) ≥ 2, where P = Petersen graph. (Thus σ(P) = 2, by Exercise 9.3.4.)