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.

Go to announcements | course information | homework list | previous homework | next homework.

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_{11}, 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_{1}, P_{2}, ..., 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.