## Homework Set IV (2/6-9)

For Mon. 2/9: Read Section 2.1.

Do for discussion Thurs. 2/12:

Sect. 2.1, ## 1-4, 8, 13, 18, and 9-10 (for P_{5}, K_{4,4}, D, and O).

## D1, D3.

Do for discussion Fri. 2/13:

Sect. 2.1, ## 6, 11, 14, 16, 17.

# D4.

Hand in Mon. 2/16:

Sect. 2.1, ## 5, 7, 15(a), 19, 20, and 9-10 (for I).

## D2, D5.

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

#### Notice

**Test I is on Thurs. 2/19**, covering everything we've done so far in book (that's up to Section 2.1, inclusive) and class (including Menger's Theorems). We will review on Wed. 2/18.

#### Corrections

- The definition of a cycle on p. 16 is valid for n >= 3 but not for n = 1 or 2.
- In the proof of Theorem 1.3.5, at the top of p. 20, insert the sentence: "Then follow P
_{2} back to v_{1}." before "Then we have a cycle."
- In Exercise 2.1 # 4, you should find

(a) any critical subgraph;

(b) a critical subgraph whose chromatic number equals that of the whole graph.
- The graph I in Figure 1.2.5 is the one without a label. (It's the icosahedral graph.)

## Problem Set D

D1. Suppose the average degree of a graph G is > 2.

(a) Prove that G contains *at least* 2 cycles.

(b) Prove that it is possible for G to have *exactly* 2 cycles.

D2. Suppose G is a connected graph whose average degree is 3.

(a) Show that G has at least 4 cycles.

(b) Is 4 the best possible number? Or can you prove that G must have 5 or more cycles? 6 or more?

D3. Find the chromatic number chi(G) where G is the graph in Figure 2.1.5.

D4. Is the graph of Figure 2.1.5 critical? Prove. (Don't believe everything you read!)

D5. Is the graph of Figure 2.1.6 critical? Prove.