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 between 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 graphical 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