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

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

#### 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_{5}), 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.)