Homework Set VI (2/24)

For Fri. 2/25: Read Section 2.3.
For Mon. 2/28: Read Sections 2.3-4.

Do for discussion Tues. 3/1:
Sect. 2.3, ## 1-3, 5-7 (for Q₃ and I), 18(a).
Sect. 2.4, ## 1, 4, 5.
## F1(a), F3(a,b), F4(a).

Do for discussion Wed. 3/2:
Sect. 2.3, ## 4, 8, 10, 12, 18(b).
Sect. 2.4, ## 2, 8.
## F1(b,c), F3(c), F4(b,c).

Hand in Fri. 3/4:
Sect. 2.3, ## 5-7 (for D), 17, 18(c).
Sect. 2.4, ## 7, 25.
## F1(d), F2, F3(d), F4(d).

Corrections

• 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 F

F1. 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.

F2. Prove that, if G is a tree, then its edge chromatic number χ'(G) equals its maximum degree Δ(G).

F3. Find a Hamilton cycle or prove there is none.
(a) Figure 2.3.4.
(b) Figure 2.3.5. (Hint: there isn't!)
(c) Figure 2.1.6.
(d) Figure 2.3.7.

F4. Let V(K_2n+1) = {0, 1, 2, ..., 2n-1, x}. We have a standard way of decomposing K_2n+1 into Hamilton cycles (see Section 2.3). In K₁₁, which "standard" Hamilton cycle contains the edge
(a) 23 ?
(b) 3x ?
(c) 46 ?
(d) 37 ?