Graphs and Networks: Isomorphism

Basic Concept

Isomorphism is a concept in graph theory where two graphs are considered isomorphic if they have the same structure, but not necessarily the same layout or labelling of vertices.
Particularly, visual representation or aesthetic orientation does not matter; it is the connection between vertices and edges that counts.

Two graphs are said to be isomorphic if they meet the following criteria:
- They have the same number of vertices.
- They have the same number of edges.
- The degree-sequence (i.e., the sequence when the degrees of each vertex are listed in non-increasing order) of both graphs is identical.
- They maintain the same connections - there exists a one-to-one correspondence between the vertices of both graphs in such a way that if two vertices are adjacent in one graph, the corresponding vertices are also adjacent in the other graph.

Isomorphisms are used in various mathematical and practical applications, including computer science algorithms for graph comparison, chemical structural analysis and sociology for analysing social networks.

If two graphs differ in a simple property such as number of vertices, degree sequence, or number of edges, they are non-isomorphic. This can be a quick way to determine non-isomorphism without needing to check the harder-to-determine property of maintaining the same connections.

For example, two graphs both have 4 vertices and 4 edges, where each vertex has degree 2. These graphs are isomorphic, because their vertices can be matched such that the connections between vertices are preserved. The specific naming or placement of the vertices doesn’t affect isomorphism.
If another graph has 4 vertices but only 3 edges, it is non-isomorphic to the previous two graphs, primarily because it doesn’t meet the second criterion of having the same number of edges.