Homework Set XIII and Problem Set M (4/30)

Read Sects. 9.2 and 9.3.

Do for discussion Wed. 5/5:
Sect. 9.2, ## 1-4, 6, 7.
Sect. 9.3, ## 1-4, 6, 8.
## M1, M3, M4(a).

Do for discussion Thurs. 5/6:
Sect. 9.3, # 7.
## M4(b), M5.

Hand in Thurs. 5/6:
Sect. 9.3, ## 5, 9.
# M2.

Definitions, Statements, and Corrections

• Theorems 9.2.1 and 9.2.2 require the assumption that p >= 3.
• The lower bound theta(K_n) >= floor[(n+7)/6] stated on page 192 is lengthy to prove. But the same formula can be rewritten as theta(K_n) >= ceiling[(n+2)/6], whose proof is easy and short. (See Problem K5.)

Problem Set M

M1. Find theta(P), where P is the Petersen graph.

M2. Prove that theta(K_n) >= ceiling[(n+2)/6] for all n >= 1.

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

M4. Let H = Heawood graph, Fig. 4.2.4.
(a) Prove sigma(H) >= 2. (Hint: One way is to use Theorem L in Homework Set XII.)
(b) We know sigma(H) <= 3. Decide whether sigma(H) = 2 or 3.

M5. Prove sigma(P) >= 2, where P = Petersen graph. (Thus sigma(P) = 2, by Exercise 9.3.4.)