Homework Set XI (4/15)

Read for Tues. 4/19: Sects. 8.2 and 8.3. (This is a lot for me to discuss on 4/15. Study carefully and come in Tuesday with many questions.)

Do for discussion Tues. 4/26:
Sect. 8.2, ## 3, 4.
Sect. 8.3, ## 2, 3.
Sect. 9.1, ## 5, 6, 14.
## K1, K3(a).

Do for discussion Wed. 4/27:
Sect. 8.3, ## 4, 7.
## K2(a,b), K3(b), K4.

Hand in Fri. 4/29:
Sect. 9.1, # 15.
Sect. 8.2, ## 5, 6.
## K2(c), K3(c), Aut.9.

Definitions and Corrections

• Exercise 8.2.6: Assume G is connected.
• Definition for Exercise 8.3.7: A plane triangulation is a plane graph in which every region is a triangle.

TEST III will be on Tuesday, May 3.

Problem Set K

K1. Prove that cr(P) ≥ 2, where P is the Petersen graph.

K2. (a) Prove that, if p ≥ 11, then K_p has no decomposition into two planar graphs.
(b) Can K₈ be decomposed into two planar graphs?
(c) Prove: if p ≥ 17, then K_p cannot be decomposed into three planar graphs.

K3. Do both (i) and (ii) for
(a) Fig. 2.3.6.
(b) Fig. 4.2.4.
(c) Fig. 1.3.3.

(i) Is the graph planar?

(ii) Find the crossing number. If you can't calculate it exactly, find out as much as you can about it. For instance, is it = 0 or > 0? Is it = 1? = 2? ≥ 2? ≥ 3? Can you find any upper bound?

K4. Write a complete proof of the 6-Color Theorem: Every planar graph can be colored in 6 colors. (Hint: Try induction on the number of vertices.)