Exercises
351
32. Prove that G and H as shown are isomorphic:
1
3
a
b
2
4
e
G
H
33. Prove that no pair of G 1 , G 2 , and G 3 as shown are isomorphic:
GI
G2
G3
34. Prove that G and H as shown are isomorphic:
1
a_
6 5•
3
f
c
5
4
e
d
G
H
35. For each graph shown in Exercise 16, construct both an adjacency matrix and an adjacency list representation.
36. Construct two different adjacency matrices and two different adjacency lists for C 4 .
37. Prove that if G = (V, E) is isomorphic to G, then I V I =_ 0, 1 (mod 4).
38. Given a self-complementary graph with 4m vertices for some m > 0, construct a selfcomplementary graph on 4m + 1 vertices that contains the self-complementary graph
on 4m vertices as an induced subgraph.
39. Construct all self-complementary graphs on four and five vertices.
40. Let G = (V, E) be a graph with I V I > 3. Prove that if the degree of each vertex in G
is at least I V 1/2, then G is Hamiltonian.
41. Let G = (V, E) be a graph. Prove that if for any two nonadjacent vertices v and w of
G we have deg(v) + deg(w) > I V 1, then G is Hamiltonian.
42. Let g be a set of graphs. For all G, H E 0, define the relation R as G R H if and only
if G and H are isomorphic. Prove that R is an equivalence relation.
43. Let A" = [a I n)] be the nth power of the adjacency matrix of G. Prove that:
(a)2, i A j, is the number of i - j paths of length 2 in G.
(2)
(b) a~i2) deg(i).
(c) (1/6)E aii is the number of 3-cycles in G.
(d) For each graph given below by its adjacency matrix representation, verify parts (a)
through (c). For each pair of vertices, determine how many paths of length 3 are