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₅, 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.

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₂ back to v₁." 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.