Exercises 351
- Prove that G and H as shown are isomorphic:
1 3 a b
2 4 e
G H
- Prove that no pair of G 1 , G 2 , and G 3 as shown are isomorphic:
GI G2 G3
- Prove that G and H as shown are isomorphic:
1 a_
6 5• 3 f c
5 4 e d
G H
- For each graph shown in Exercise 16, construct both an adjacency matrix and an adja-
cency list representation.
- Construct two different adjacency matrices and two different adjacency lists for C 4.
- Prove that if G = (V, E) is isomorphic to G, then I V I =_ 0, 1 (mod 4).
- Given a self-complementary graph with 4m vertices for some m > 0, construct a self-
complementary graph on 4m + 1 vertices that contains the self-complementary graph
on 4m vertices as an induced subgraph.
- Construct all self-complementary graphs on four and five vertices.
- 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.
- 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.
- 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.
- 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.
(b) a~i2) (2) 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
