Homework Set V (2/20)

For Mon. 2/23: Read Sections 2.2, 2.3.

Do for discussion Thurs. 2/26:
Sect. 2.2, ## 3, 5, 6, 8, 9.
Sect. 2.3, ## 1, 3, 5.
## E1(a), E3(a).

Do for discussion Fri. 2/27:
Sect. 2.3, ## 4, 6-7 (for Q₃ and I), 8, 10, 18(a).
## E2, E3(b-c).

Hand in Mon. 3/1:
Sect. 2.2, ## 4, 7, 10.
Sect. 2.3, ## 2, 5-7 (for D), 18(c).
## E1(b), E3(d).

Corrections

• The graph I in Figure 1.2.5 is the one without a label. (It's the icosahedral graph.)
• Theorem 2.2.4 is valid only for n >= 2.
• The last line on p. 38 (the one for (C_n)) should read
  n-1, n-2, n, n-3, n+1, n-4, ..., 2n-2, 2n-1, x.
  
  (This is actually equivalent to the printed line, but the printed line doesn't follow the pattern it's supposed to.)

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.

E3. Let V(K_2n) = {0, 1, 2, ..., 2n-2, x}. We have a standard way to decompose K_2n into 1-factors (see Section 2.2). In K₈, which "standard" 1-factor contains the following edge? (For your answer you may list all edges that belong to the 1-factor.)
(a) 23.
(b) 2x.
(c) 36.
(d) 15.