Page 709 - Discrete Mathematics and Its Applications

688 10 / Graphs

To find a possible isomorphism, we can follow paths that go through all vertices so that the
corresponding vertices in the two graphs have the same degree. For example, the paths u 1 , u 4 ,
u 3 , u 2 , u 5 in G and v 3 , v 2 , v 1 , v 5 , v 4 in H both go through every vertex in the graph; start at a
vertex of degree three; go through vertices of degrees two, three, and two, respectively; and end
at a vertex of degree two. By following these paths through the graphs, we define the mapping f
with f(u 1 ) = v 3 , f(u 4 ) = v 2 , f(u 3 ) = v 1 , f(u 2 ) = v 5 , and f(u 5 ) = v 4 . The reader can show
that f is an isomorphism, so G and H are isomorphic, either by showing that f preserves edges
or by showing that with the appropriate orderings of vertices the adjacency matrices of G and H
are the same. ▲

Counting Paths Between Vertices

The number of paths between two vertices in a graph can be determined using its adjacency
matrix.

THEOREM 2 Let G be a graph with adjacency matrix A with respect to the ordering v 1 , v 2 ,..., v n of
the vertices of the graph (with directed or undirected edges, with multiple edges and loops
allowed). The number of different paths of length r from v i to v j , where r is a positive integer,
r
equals the (i, j)th entry of A .

Proof: The theorem will be proved using mathematical induction. Let G be a graph with adja-
cency matrix A (assuming an ordering v 1 , v 2 ,..., v n of the vertices of G). The number of paths
from v i to v j of length 1 is the (i, j)th entry of A, because this entry is the number of edges
from v i to v j .
r
Assume that the (i, j)th entry of A is the number of different paths of length r from v i
r
to v j . This is the inductive hypothesis. Because A r+1 = A A, the (i, j)th entry of A r+1 equals
b i1 a 1j + b i2 a 2j + ··· + b in a nj ,

r
where b ik is the (i, k)th entry of A . By the inductive hypothesis, b ik is the number of paths of
length r from v i to v k .
A path of length r + 1 from v i to v j is made up of a path of length r from v i to some
intermediate vertex v k , and an edge from v k to v j . By the product rule for counting, the number
of such paths is the product of the number of paths of length r from v i to v k , namely, b ik , and
the number of edges from v k to v j , namely, a kj . When these products are added for all possible
intermediate vertices v k , the desired result follows by the sum rule for counting.

EXAMPLE 15 How many paths of length four are there from a to d in the simple graph G in Figure 8?

a b
Solution: The adjacency matrix of G (ordering the vertices as a, b, c, d)is
⎡ ⎤
0 1 1 0
1 0 0 1
⎢ ⎥
A = ⎢ ⎥ .
⎣ 1 0 0 1 ⎦
d c 0 1 1 0
4
FIGURE 8 The Hence, the number of paths of length four from a to d is the (1, 4)th entry of A . Because
Graph G.
⎡ ⎤
8 0 0 8
4 ⎢ 0 8 8 0 ⎥
A = ⎢ ⎥ ,
⎣ 0 8 8 0 ⎦
8 0 0 8