Discrete Mathematics for Computer Science

414 CHAPTER 6 Graph Theory

2. Prove that G has no Hamiltonian cycle that contains the edge (e, j).

a

h

g e c

f d

G

3. Prove that the G and H are isomorphic.

1 2

5 4 j h

G H

4. Let G and H be graphs, and let v E V(G). Let F: G - H be an isomorphism be-
   tween G and H. Let edges (v, w), (w, y), (y, x), and (x, v) form a 4-cycle in G. Prove
   that the images of these edges under F form a 4-cycle in H.


5. Construct the Dfs and Bfs trees for the following graph starting at vertex 1: Assume
   the adjacency lists are formed by listing the adjacencies of each vertex in increasing
   order.

9 2

12

10 1

8 413

811 t•

14

7 154

6 5

6. Let G = (V, E) be a graph. Prove that if 8(G) and A (G) represent the minimum and
   the maximum degrees of all the vertices of G, respectively, then

b(6) < 2. - E1l/Il <_ A(G)

7. Prove by induction that the sequence 1, 1, 2, 2, 3, 3 .... n - 1, n - 1, n, n is graphi-
   cal for all n such that n > 1.


8. Let G = (V, E) with I V >__ 2 be a graph with all vertex degrees occurring exactly
   once except for a single degree that occurs twice. Find the value(s) for the repeated