Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Graph Theory"
Read Section 1.6. Isomorphism of two graphs is a formal way of saying that two graphs are essentially the same. Essentially the same means that they are the same with respect to specified properties that characterize a graph.
Let G and H be two graphs. To show G and H are isomorphic, construct a bijection from the vertices of G to the vertices of H that preserves adjacency. The adjacency matrix, defined in section 4, is helpful in supping the construction of an isomorphic mapping.
G and H are not isomorphic if:
- there is no bijection from the vertices of G to H;
- there is no bijection that preserves adjacency of vertices; and
- G and H have different properties, e.g. vertices have different degrees.