For Mon. 2/7: Read Section 2.1.
Do for discussion Wed. 2/9:
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/11:
Sect. 2.1, ## 6, 11, 14, 16, 17.
# D4.
Hand in Mon. 2/14:
Sect. 2.1, ## 5, 7, 15(a), 19, 20, and 9-10 (for I).
## D2, D5.
D1. Suppose the average degree of a graph G is > 2. [Note: This should have said G is connected. – 2/18]
(a) Prove that G contains at least 2 cycles.
(b) Prove that it is possible for G to have exactly 2 cycles.
A solution is available here. (Hint for D2: Use a similar idea, but you have to add something.)
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 χ(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.