Exercises 349

identify:

(a) the degree of each vertex

(b) a path of length greater than four, if any exists

(c) a cycle of size greater than four, if any exists

(d) a trail of length six, if one exists

(e) one circuit with more edges than the number of vertices in the graph, if one exists

17. For the graph

6 \-2

5, 3

4

do the following:

(a) Find subgraphs without isolated vertices that are n-regular for n = 2, 3, 4, 5.

(b) Find one path for each of the lengths three, four, five, and six.

(c) Find one cycle of each of the sizes three, four, five, and six.

(d) Find one trail for each of the lengths 6, 8, 10, and 12.

(e) Find the induced subgraphs determined by the sets of vertices {1, 3, 4}, {2, 3, 5,

6}, {2, 4, 6}, and {1, 3, 4, 5, 61.

The solutions for parts (a), (b), (c), and (e) should be drawings of graphs with the

vertices labeled as in the figure. For part (d), list the vertices as they occur in the trail.

18. Prove that if a graph G has an n-circuit with n odd and n > 3, then G has an odd
    cycle.


19. Show that 1, 2, 2, 3, 4 is graphical but that 1, 3, 3, 3 is not. Prove the theorem of
    Havel-Hakimi that for n > 1, the sequence dl, d 2 ..... d, is graphical if and only if
    d, d2, .... dn-d,, dnd,+1 - 1 ... , dn-I - 1 is graphical.


20. Let d, d2. .... , d, be a sequence of distinct integers where n > 1 and 0 < di <_ n - 1
    for 1 < i < n. Prove that such a sequence is not graphical.

21. Let G = (V, E) be a bipartite graph with vertex partition V = A U B. Prove that if

I A A I B 1, then G is not Hamiltonian.

22. Find a Hamiltonian cycle in Q3.


23. Find a Hamiltonian cycle in the following graphs:

I I

1

5 K 2 7 891

6 1* 3

(^10 13 12)
(^4 3 5 4)
G, G2