Isomorphic graph

Two graphs are isomorphic if they have the same structure.

This means that their adjacency matrix will produce two identical graphs (ignoring the vertex labels.

In other words, we can redraw the graph to make them look identical, even if the vertices and edges are labelled differently.

Example

These two graphs are isomorphic:

Graph 1:        Graph 2:
 A --- B        1 --- 2
 |     |        |     |
 C --- D        3 --- 4

Even though the vertices are labeled differently (A, B, C, D vs. 1, 2, 3, 4), the connections between them are the same. We can map A to 1, B to 2, C to 3, and D to 4.

Checking for isomorphism

To check if two graphs are isomorphic, we can look at:

• The number of vertices and edges in each graph.
• The degree of each vertex (how many edges connect to it).
• The overall structure and connections between vertices. If all these aspects match, the graphs are isomorphic!

Complete graph

Two complete graphs with the same order will be isomorphic.