Discrete Mathematics for Computer Science

350 CHAPTER 6 Graph Theory

24. Find a Hamiltonian cycle in the following graph:

a

bp t

<^0

d h

e 9 k Ir

G H

S

f

Cl'

25. Complete the proof of Example^5 in Section 6.3. 1.


26. Complete the proof of Case ii of Example 6 in Section 6.3. 1.

27. Show that the function F(a) = 3, F(b) = 1, F(c) = 4, and F(d) th2 is an isomor-

phism between the graphs G and H as shown:

a b^1 2

V3

d C^4

G H

28. Prove that for two graphs G and H that G is isomorphic to H if and only if G is
    isomorphic to R.


29. Let G = (V, E) and H =(V 1 , EI) be isomorphic graphs. Prove the degrees of the

vertices of G are exactly the degrees of the vertices of H. Show that IV =V, and

I E I = I EI alone do not imply that G and H are isomorphic.

30. Prove that G and H as shown are isomorphic:

1 2 a

5 4 a b

A d

f

G H

3 1. Prove that G and H as shown are not isomorphic:

4 ab

G H