Homework Set V (2/12)

For Mon. 2/14: Read Section 2.2.

Do for discussion Wed. 2/16:
Sect. 2.2, ## 3, 5, 6, 8, 9.
# E1(a).

Hand in Fri. 2/18:
Sect. 2.2, ## 4, 7, 10.
## E1(b), E2.

Problem Set E

E1. Prove there is no 1-factor in the graph of Figure 2.2.6 (a) left, (b) right.

E2. Is the graph of Figure 2.1.2 critical? Prove.

Do for discussion Tues. 2/22:
## EE1-EE3.

The first example graph theorists look at when they have a complicated new idea is K_p. The next one could be G = K_p - edge.

EE1. Find the chromatic number χ(G).

EE2. Find the edge chromatic number χ'(G) when p is even, i.e., p = 2n (n ≥ 1).

EE3. Find the edge chromatic number χ'(G) when p is odd, i.e., p = 2n-1 (with n ≥ 2).