Homework Set VI and Problem Set F (2/27)

Read Section 2.4.

Do for discussion Thurs. March 4:
Sect. 2.3, ## 12, 17.
Sect. 2.4, ## 1, 3, 5, 8, 10.
## F1(a, b), F2(a).

Do for discussion Fri. March 5:
Sect. 2.3, # 18(b).
Sect. 2.4, ## 4, 12, 21.
## F1(d), F2(b, c), F4.

Hand in Mon. March 8:
Sect. 2.4, ## 7, 9 (Fig. 2.3.7), 22, 25.
## F1(c), F2(d), F3.

Problem Set F

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

F2. 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 ?

F3. Prove that K_p can be decomposed into p - 1 paths P₁, P₂, ..., P_p-1 for all values of p, not only the even values to which Theorem 2.3.4 applies.

F4. Verify that, in the proof of Theorem 2.3.2, the first two 1-factors unite to form a Hamilton cycle. Your proof should be valid for all n >= 2.