Homework Set VIII and Problem Set H (3/10)

Read Sects. 3.2 and 3.3.

Do for discussion Thurs. 3/18:
Sect. 3.2, ## 1-3, 8.
Sect. 3.3, ## 1-4, 6.

Do for discussion Fri. 3/19:
Sect. 3.2, ## 4, 6.
Sect. 3.3, ## 7, 8, 17.
## H1, H2.

Hand in Mon. 3/22:
Sect. 3.2, ## 5.
Sect. 3.3, ## 16, 20.
## H3, H4.

Correction

In Exercise 3.3.17, the graph you find should also be connected, in addition to the other properties that were specified.

Problem Set H

H1. (a) Find a graph E which has an Eulerian circuit but no Hamilton cycle.
(b) Find a graph H which has a Hamilton cycle but no Eulerian circuit.

H2. Produce a decomposition of Fig. 3.2.8 into two 2-factors, using the method of proof of Theorem 3.1.4.

H3. Correction: This is the same as # F3. Please omit. 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.

H4. For ambitious students, prove:
Lemma H4. In a pseudograph G, if there is a trail with endpoints a and b, then there is a path with endpoints a and b.