Homework Set XI and Problem Set K (4/14)

Read for Mon. 4/19: Sect. 8.3; and also Sect. 8.2, omitting the part about edge 3-coloring (Theorem 8.2.1, Theorems 8.2.3-5, and Theorem 8.2.7). The points to focus on are: coloring a map, mormal maps, Lemma 8.2.2, and the dual graph.

Read for Wed. 4/21: Sect. 8.4.

Do for discussion Thurs. 4/22:
Sect. 8.2, ## 3, 4.
Sect. 8.3, ## 2, 3.
Sect. 8.4, ## 1, 2, 4, 7.
Sect. 9.1, ## 5, 6, 14.
## K1, K3(a).

Do for discussion Fri. 4/23:
Sect. 8.3, ## 4, 7.
Sect. 8.4, ## 5, 9.
## K2(a,b), K3(b), K4.

Hand in Mon. 4/26:
Sect. 9.1, # 15.
Sect. 8.2, ## 5, 6.
Sect. 8.4, ## 3, 6, 11.
## K2(c), K3(c).

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.
• 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.
• Definition: A plane drawing (of a graph) is called stretchable if its edges can be straightened--the vertices can be shifted around if necessary. (I'll discuss this in class.)
• The proof of Theorem 8.4.1 is not stated exactly right in the book. In the middle, what is stretchable is not G - h but the plane drawing of it that we already have. So what we have to prove is not that all planar graphs are stretchable, but that all plane drawings are stretchable.

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