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 P5, K4,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.
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.
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.