Graph Isomorphism Explained: Detection Tests and a Worked Mapping

Learn how to reject non-isomorphic graphs quickly, construct and verify a full bijection, and avoid treating equal degree sequences as proof.

KnowledgeGate Team

Exam prep & CS education

Updated 10 Nov 20266 min read
Graph Isomorphism Explained: Detection Tests and a Worked Mapping

Graph isomorphism asks whether two drawings encode the same adjacency structure under a relabelling. Equal vertex counts, edge counts, and degree sequences can reject some candidates but cannot prove a match. A positive result needs a complete adjacency-preserving bijection, verified edge by edge or through matched adjacency matrices. If paths and cycles need revision first, review Euler, Hamiltonian and graph colouring.

1. Graph isomorphism: same structure under different labels

Let G = (V_G, E_G) and H = (V_H, E_H) be simple undirected graphs. They are isomorphic if there is a bijection f: V_G -> V_H such that, for every pair u, v,

{u,v} in E_G if and only if {f(u),f(v)} in E_H.

The bijection maps every vertex of G once, gives no two source vertices the same image, and preserves adjacency and non-adjacency.

Names, list order, page position, crossings, and edge shape are presentation choices. Isomorphism relabels structure; it is not a geometric transformation.

Isomorphic graphs must have equal vertex and edge counts, sorted degrees, component sizes, counts of cycles of each length, and equal numbers of cut vertices and bridges. One invariant mismatch proves non-isomorphism. Matches only keep isomorphism possible.

2. A reliable detection workflow: reject, refine, map, verify

Use four stages:

  1. Reject: compare |V|, |E|, sorted degrees, components, bipartiteness, and triangles.

  2. Refine: assign each vertex a signature from its degree, neighbour degrees, triangle membership, and useful distances.

  3. Map: form candidates from matching signatures, then extend a bijection vertex by vertex.

  4. Verify: check every pair, or compare matrices in matched vertex order.

For u -> x, reject the branch if x is used, signatures differ, or an earlier v -> y makes uv and xy disagree about adjacency. Next choose the vertex with the smallest candidate set or most distinctive signature.

A sound solution gives a verified bijection or one differing invariant. Drawing intuition is not proof. Use the solved Graph Theory MCQs for broader practice.

3. Fully worked example: construct the isomorphism

Take

V_G = {a,b,c,d,e,f}

E_G = {ab, bc, ac, cd, de, ef, df, fa}

and

V_H = {1,2,3,4,5,6}

E_H = {14, 16, 46, 36, 35, 25, 23, 24}.

Every listed edge is unordered. Both graphs have 6 vertices, 8 edges, one component, two triangles, and sorted degrees (3,3,3,3,2,2). These necessary checks are not proof.

The degree-2 vertices are {b,e} in G and {1,5} in H. Choose b -> 1. Since N_G(b) = {a,c} and N_H(1) = {4,6}, choose a -> 4 and c -> 6. Edge cd forces the unused degree-3 neighbour d -> 3. Degree then forces e -> 5 and f -> 2.

The resulting bijection is

f(a)=4, f(b)=1, f(c)=6, f(d)=3, f(e)=5, f(f)=2.

Now verify all source edges:

Edge in G

Image in H

ab

14

bc

16

ac

46

cd

63

de

35

ef

52

df

32

fa

24

Because edges are unordered, 63, 52, and 32 equal 36, 25, and 23. The image set is exactly E_H, all images are distinct, and H has no extra edge. Adjacency and non-adjacency are preserved, so the graphs are isomorphic. This need not be the only valid mapping.

Two 6-vertex, 8-edge graphs side by side, with arrows mapping a-4, b-1, c-6, d-3, e-5, f-2; both have degree sequence (3,3,3,3,2,2).

4. Verify the mapping with adjacency matrices

Order G as (a,b,c,d,e,f). Its adjacency matrix is:

Code
0 1 1 0 0 1
1 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 1
1 0 0 1 1 0

It is symmetric, its diagonal is zero, and its row sums are (3,2,3,3,2,3).

Now order H by the images of the source order: (4,1,6,3,5,2). Its matrix is the same:

Code
0 1 1 0 0 1
1 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 1
0 0 0 1 0 1
1 0 0 1 1 0

Thus A_G[i,j] = A_H[f(i),f(j)] for every pair. One simultaneous permutation of corresponding rows and columns makes the matrices equal. Permuting only rows, or using different permutations on the axes, proves nothing.

5. Why matching degrees is not enough

The trap does not need a regular graph. Let X have vertex set {1,2,3,4,5,6} and edges {12,13,23,34,45,56,61}, and let Y have the same vertices with edges {12,23,34,45,56,61,14}.

Both are connected, with 6 vertices, 7 edges, and sorted degrees (3,3,2,2,2,2); the degree-3 vertices are 1 and 3 in X, and 1 and 4 in Y. Counts, components, and degrees all match. Yet X contains the triangle 1-2-3, while Y is the six-cycle 1-2-3-4-5-6-1 plus the chord 14, whose shortest cycles are 1-2-3-4-1 and 1-4-5-6-1. Graph Y has no triangle, so no bijection can preserve adjacency and the two graphs are not isomorphic.

The same trap appears at a regular degree sequence. Let P be the triangular prism with vertices {1,2,3,4,5,6} and edges {12,23,31,45,56,64,14,25,36}. Let B be K_3,3, with partitions {a,b,c} and {x,y,z}, containing all nine cross edges {ax,ay,az,bx,by,bz,cx,cy,cz}.

Both are connected with 6 vertices, 9 edges, and degrees (3,3,3,3,3,3). Yet P contains triangles 1-2-3-1 and 4-5-6-4. Graph B is bipartite, so every cycle has even length and its triangle count is 0. These properties are preserved, so the graphs are not isomorphic.

K_3,3 can support different graph-theory arguments. Planar Graphs and Kuratowski's Theorem uses it as a forbidden planarity obstruction. Here it is only a 3-regular, triangle-free counterexample to the claim that matching degree sequences prove isomorphism.

Basic invariants narrow the search but never certify a mapping. If they match, inspect triangles, odd cycles, component sizes, bridges, cut vertices, and distances.

Prism P beside bipartite graph B: both have 6 vertices, 9 edges and all degrees 3, but P shows two shaded triangles and B has none.

6. Common graph-isomorphism traps

Wrong move

Consequence

Correction

Equal vertex and edge counts mean isomorphic

Counts are mistaken for proof

Use counts only as filters

Equal degree sequences mean isomorphic

Different structures pass

Compare richer invariants, then map

Drawings look different

Geometry is confused with structure

Ignore placement and crossings

Two sources map to one target

The function is not bijective

Use each target once

Several mapped edges work

A later edge or a non-adjacent pair can still fail

Verify every pair or matched matrices

An automorphism maps a graph isomorphically to itself. Whole-graph isomorphism maps every vertex between two graphs. Subgraph isomorphism asks whether one graph occurs inside part of another, so it does not assume equal vertex counts.

7. How questions test graph isomorphism

Questions may ask you to choose a pair, complete a mapping, find a decisive invariant, assess equal degrees, reorder a matrix, or test a proposed map.

Here, b -> 1 leads to (a,b,c,d,e,f) -> (4,1,6,3,5,2), and eight edge images equal E_H. In the prism counterexample, degrees are all 3, but triangle counts are 2 and 0. Thus "Equal sorted degree sequences imply isomorphism" is false.

On scratch paper, write n, m; sort degrees; compare components, bipartiteness, and triangles; mark distinctive vertices; build candidates; then verify pairs or matrices.

8. Graph isomorphism short version and next step

Invariants can disprove isomorphism quickly, but a positive result needs an adjacency-preserving bijection. Here, 6 vertices, 8 edges, and degrees (3,3,3,3,2,2) guided the search. The mapping (a,b,c,d,e,f) -> (4,1,6,3,5,2) and eight edge images completed the proof.

For a self-test, hide the mapping, start with e -> 5, reconstruct it, and verify all eight images. Then explain why the prism and K_3,3 fail despite being connected 3-regular graphs on six vertices. The decisive phrase is: two triangles versus no odd cycle.

Use GATE CS courses and preparation for broader preparation. GATE Guidance by Sanchit Sir offers an optional structured sequence including Discrete Mathematics and Graph Theory. It is not a prerequisite for this method.