Homework Set VIII (3/10,12)

For Mon. 3/14: Read Section 3.2.

Do for discussion Tues. 3/15:
Sect. 3.2, ## 1-3, 8.
## H1, H2, H5(a), H6(a).
And continued from last week: 2.4 # 12 (see correction), and 3.1 ## 8, 13.

Do for discussion Wed. 3/16:
Sect. 3.2, ## 4, 6.
## H5(b,c), H6(b,c).

Hand in Fri. 3/18:
Sect. 3.2, ## 5.
## H3, H4, H5(d), H6(d).

Homework Set VIIIa (3/12,15)

For Fri. 3/18: Read Section 3.3. (This will not be tested. We'll discuss infinite graphs, just to see the weird differences.)

Additional topic for Fri. 3/18: Line graphs. (This is not in the book. It will not be on Test II but it will probably be on Test III.)

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

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. Prove that Kp can be decomposed into p - 1 paths P1, P2, ..., Pp-1 for all values of p, not only the even values to which Theorem 2.3.4 applies.

H4. For ambitious students, prove rigorously:
    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.

H5. Use the proof method of Theorem 3.2.4 to decompose into subgraphs isomorphic to P3 :

  1. the Petersen graph, Fig. 1.1.13,
  2. the icosahedral graph I in Fig. 1.2.5,
  3. Fig. 2.3.4,
  4. the Tutte graph, Fig. 2.3.5.

H6. Use the proof method of Theorem 3.1.7 (Listing's Theorem) to decompose into the smallest possible number of trails:

  1. the Petersen graph, Fig. 1.1.13,
  2. Fig. 2.3.6,
  3. Fig. 2.3.7,
  4. the Grötzsch graph, Fig. 2.1.6.

H7. (Optional: research problem.) We know some cubic graphs can be decomposed into P3 subgraphs (e.g., Figs. 2.4.1-2), and some cannot (e.g., Fig. 2.2.6). The counterexample (Fig. 2.2.6) has a bridge, in fact it has three. Must every counterexample have a bridge? That is, can we say that every cubic graph which is connected and has no bridges can be decomposed into P3 subgraphs?