Paths And Isomorphism

Paths and Isomorphism: There are several ways that paths and circuits can help determine whether two graphs are isomorphic. For example, the existence of a simple circuit of a particular length is a useful invariant that can be used to show that two graphs are not isomorphic. In addition, paths can be used to construct mappings that may be isomorphisms.

As we mentioned, a useful isomorphic invariant for simple graphs is the existence of a simple circuit of length k, where k is a positive integer greater than 2.  Example 1 illustrates how this invariant can be used to show that two graphs are not isomorphic.

EXAMPLE 1 Determine whether the graphs G and H shown in Figure 6 are isomorphic.
Solution: Both G and H have six vertices and eight edges. Each has four vertices of degree three, and two vertices of degree two. So, the three invariants—number of vertices, number of edges, and degrees of vertices—all agree for the two graphs. However, H has a simple circuit of length three, namely, v1, v2, v6, v1, whereas G has no simple circuit of length three, as can be determined by inspection (all simple circuits in G have length at least four). Because the existence of a simple circuit of length three is an isomorphic invariant, G and H are not isomorphic.

We have shown how the existence of a type of path, namely, a simple circuit of a particular length, can be used to show that two graphs are not isomorphic. We can also use paths to find mappings that are potential isomorphisms.

EXAMPLE 2 Determine whether the graphs G and H shown in Figure 7 are isomorphic.
Solution: Both G and H have five vertices and six edges, both have two vertices of degree three and three vertices of degree two, and both have a simple circuit of length three, a simple circuit of length four, and a simple circuit of length five. Because all these isomorphic invariants agree, G and H may be isomorphic.

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 u1, u4, u3, u2, u5 in G and v3, v2, v1, v5, v4 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 (u1) = v3, f (u4) = v2, f (u3) = v1, f (u2) = v5, and f (u5) = v4. 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 ofGand 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 v1, v2, . . . , vn 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 vi to vj , where r is a positive integer, equals the (i, j )th entry of Ar .
Proof: The theorem will be proved using mathematical induction. Let G be a graph with adjacency matrix A (assuming an ordering v1, v2, . . . , vn of the vertices of G). The number of paths from vi to vj of length 1 is the (i, j )th entry of A, because this entry is the number of edges from vi to vj .

Assume that the (i, j )th entry of Ar is the number of different paths of length r from vi to vj . This is the inductive hypothesis. Because Ar 1 = ArA, the (i, j )th entry of A_{r 1} equals
b_i1a_1j b_i2a_2j · · · b_ina_nj ,
where bik is the (i, k)th entry of Ar . By the inductive hypothesis, bik is the number of paths of length r from vi to vk.

A path of length r 1 from vi to vj is made up of a path of length r from vi to some intermediate vertex vk, and an edge from vk to vj . By the product rule for counting, the number of such paths is the product of the number of paths of length r from vi to vk, namely, bik, and the number of edges from vk to vj , namely, akj . When these products are added for all possible intermediate vertices vk, the desired result follows by the sum rule for counting.

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

Solution: The adjacency matrix of G (ordering the vertices as a, b, c, d) is

Hence, the number of paths of length four from a to d is the (1, 4)th entry of A⁴. Because

there are exactly eight paths of length four from a to d. By inspection of the graph, we see that a, b, a, b, d; a, b, a, c, d; a, b, d, b, d; a, b, d, c, d; a, c, a, b, d; a, c, a, c, d; a, c, d, b, d; and a, c, d, c, d are the eight paths of length four from a to d.