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 isomorphism 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