Isomorphism Tests for Graphs

All of the following conditions are necessary for two graphs to be isomorphic:
1. They must have the same number of vertices.
2. They must have the same number of edges.
3. They must have the same number of connected components.
4. They must have the same number of vertices of each degree.
5. They must have the same number of cycles of each length.

Proving that Two Graphs Are Not Isomorphic

Figure 15.8 shows three graphs, to be compared with the two isomorphic graphs. Each of these graphs has eight vertices, so each could be isomorphic to those two graphs. Graph G1 is not isomorphic to those two graphs because it has only 14 edges. The graphs in Figure 15.7 each have 16 edges. Graph G2 does have 16 edges. But it is not isomorphic to the two graphs in Figure 15.7 because it has two connected components. Each of the two graphs in Figure 15.7 has only one connected component.
 

Condition 3 of Theorem 15.5 says that isomorphic graphs must have the same number of connected components. Graph G3 has 16 edges and only one connected component. But it is still not isomorphic to the two graphs in Figure 15.7 because it has some vertices of degree 3 (and some of degree 5). All the vertices of the two graphs in Figure 15.7 have degree 4. Condition 4 of Theorem 15.5 says that isomorphic graphs must have the same number of vertices of each degree.
 

Here is Figure 15.7

Theorem. Graph Isomorphism Is an Equivalence Relation
The isomorphism relation among graphs satisfies the three properties of an equivalence relation:
1. Every graph is isomorphic to itself.
2. If G1 is isomorphic to G2 then G2 is isomorphic to G1 .
3. If G1 is isomorphic to G2 and G2 is isomorphic to G3 , then G1 is isomorphic
to G3.

It took me a long time to type

Source: Schaum's Outline of Data Structures with Java 2nd Edition
by John R. Hubbard