Isomorphic Graphs

Definition

Two graphs $G_1$ and $G_2$ are said to be isomorphic if there exists a one-to-one and onto mapping between their vertex sets such that adjacency is preserved.

In simple terms, a function $f: V(G_1) \to V(G_2)$ is an isomorphism if:

• every vertex of $G_1$ corresponds to exactly one vertex of $G_2$,
• every edge in $G_1$ corresponds to an edge in $G_2$,
• if two vertices are connected in $G_1$, then their images are connected in $G_2$,
• and if two vertices are not connected in $G_1$, their images are not connected in $G_2$.

So, graphs $G_1$ and $G_2$ are isomorphic when they have the same structure, even if their drawings or labels are different.

Example:

If graph $G_1$ has edges $(A,B), (B,C), (C,A)$ and graph $G_2$ has edges $(1,2), (2,3), (3,1)$, then the graphs are isomorphic because both are triangles.

Main Content

1. Graph Structure and Vertex Relabeling

• The most important idea in isomorphism is that graphs are considered equal only by their structure, not by their names or appearance. A graph can be redrawn in many ways, but as long as the pattern of connections remains unchanged, the graph represents the same structure.
• Isomorphism involves relabeling the vertices of one graph to match the other. This relabeling must preserve adjacency exactly. If one vertex is connected to three others in the first graph, its corresponding vertex in the second graph must also be connected to three others.

Example:

• Graph $G_1$: vertices $A, B, C, D$ with edges $AB, BC, CD, DA$
• Graph $G_2$: vertices $1, 2, 3, 4$ with edges $12, 23, 34, 41$

These two graphs are isomorphic because both form a cycle of length 4.

A useful way to think about this is to imagine two different maps of the same city. Street names may change, but if intersections and roads are connected in the same way, the underlying network remains the same.

2. Conditions for Two Graphs to be Isomorphic

• Two graphs must have the same number of vertices and the same number of edges to be isomorphic. If these basic quantities differ, the graphs cannot be isomorphic.
• The degree sequence must also match. The degree of a vertex is the number of edges incident to it. If one graph has a vertex of degree 4 and the other does not, the graphs are not isomorphic.

Important checks include:

• same number of vertices,
• same number of edges,
• same degree sequence,
• same number of vertices of each degree,
• same adjacency patterns.

Example of non-isomorphic graphs:

• Graph $G_1$ is a star with one central vertex of degree 3 and three outer vertices of degree 1.
• Graph $G_2$ is a path with 4 vertices, having degrees $1, 2, 2, 1$.

Even though both graphs have 4 vertices and 3 edges, they are not isomorphic because their degree sequences are different.

This means that matching numbers alone is not enough; the internal arrangement of connections must also match.

3. Methods to Test Isomorphism

• One common method is to compare graph invariants such as number of vertices, number of edges, degree sequence, cycles, and connected components. These properties are preserved under isomorphism and can quickly rule out non-isomorphic graphs.
• If the basic properties match, we try to construct a one-to-one correspondence between the vertices. This is usually done by checking which vertices must correspond based on their degrees and neighboring vertices.

Step-by-step idea:

• Compare basic properties.
• Identify unique vertices, such as the only vertex with a certain degree.
• Try possible mappings.
• Verify whether every edge in one graph matches an edge in the other.
• If all adjacency relations are preserved, the graphs are isomorphic.

Example: Suppose two graphs each have:

• 5 vertices,
• 6 edges,
• degree sequence $3, 3, 2, 2, 2$.

We then examine which vertices have degree 3 and which have degree 2. If the arrangement of adjacent vertices also matches, an isomorphism may exist.

A helpful representation is the adjacency matrix. Two graphs are isomorphic if one adjacency matrix can be converted into the other by simultaneously permuting rows and columns in the same way. This is a powerful algebraic method for testing graph isomorphism.

Working / Process

1. Check basic graph properties

• Compare the number of vertices, number of edges, degree sequences, and connected components.
• If any of these differ, the graphs are not isomorphic.
• This step quickly eliminates many impossible cases.

2. Find a vertex correspondence

• Look for vertices with unique properties such as highest degree, lowest degree, or special positions in cycles.
• Match these vertices first because they reduce ambiguity.
• Continue matching neighboring vertices carefully.

3. Verify adjacency preservation

• For every edge in the first graph, check that the corresponding pair of mapped vertices is also an edge in the second graph.
• Also ensure that non-adjacent vertices remain non-adjacent.
• If every connection matches perfectly, the graphs are isomorphic.

Example process:

Graph $G_1$: triangle with a pendant vertex attached to one corner
Graph $G_2$: same structure but drawn differently

• Both have 4 vertices and 4 edges.
• Both have degree sequence $3, 2, 2, 1$.
• The vertex of degree 3 in $G_1$ must match the vertex of degree 3 in $G_2$.
• The pendant vertex of degree 1 must match the pendant vertex of degree 1.
• After mapping the remaining vertices, all edges correspond correctly.
• Therefore, the graphs are isomorphic.

Advantages / Applications

Graph comparison and classification

• Isomorphism helps determine whether two graphs represent the same structure, which is essential in studying mathematical networks and classifying graph families.

Computer science and data structures

• It is used in network analysis, compiler design, database searching, pattern recognition, and automorphism detection in algorithms.

Chemistry and biology

• Isomorphic graph ideas are used to compare molecular structures, where atoms are vertices and bonds are edges, helping identify whether two compounds have the same connectivity.

ASCII diagram for a simple isomorphic pair:

Graph 1:

A---B
|   |
D---C

Graph 2:

1---2
|   |
4---3

These two graphs are isomorphic because both are 4-cycles. A possible correspondence is:

• A ↔ 1
• B ↔ 2
• C ↔ 3
• D ↔ 4

This concept is also useful in:

• finding duplicate network structures,
• studying symmetry in graphs,
• solving puzzle problems in discrete mathematics,
• analyzing social and transportation networks.

Summary

• Isomorphic graphs have the same structure even if they are drawn differently or have different labels.
• A valid isomorphism is a one-to-one correspondence between vertices that preserves adjacency.
• Checking vertices, edges, degree sequence, and neighborhood structure helps determine whether two graphs are isomorphic.
• Important terms to remember: graph isomorphism, adjacency preservation, degree sequence, vertex mapping, and graph structure.