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

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

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