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

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:
Reject: compare
|V|,|E|, sorted degrees, components, bipartiteness, and triangles.Refine: assign each vertex a signature from its degree, neighbour degrees, triangle membership, and useful distances.
Map: form candidates from matching signatures, then extend a bijection vertex by vertex.
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 | Image in |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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.

4. Verify the mapping with adjacency matrices
Order G as (a,b,c,d,e,f). Its adjacency matrix is:
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 0It 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:
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 0Thus 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.

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.
Keep learning
Graph Isomorphism MCQs and NATs: 12 Solved Questions on Detection and Counting
Solve seven MCQs and five numerical-answer questions on graph isomorphism. Each answer shows the invariant, mapping or counting argument behind the result.
Degree Sequences and Graph Isomorphism for GATE: Handshake Lemma and Havel-Hakimi Drills
Use the Handshake Lemma and Havel-Hakimi mechanically, then learn why matching degree sequences cannot by themselves prove graph isomorphism.
Data Link Layer Error Control: Detection, Correction and ARQ with One End-to-End Example
Follow one frame through error detection, local correction and retransmission, with explicit CRC, ARQ timing and Hamming(7,4) calculations.
CSMA/CD Explained: Collision Detection, Binary Backoff and Solved Numericals
Learn why carrier sensing cannot prevent every collision, then solve propagation, minimum-frame, backoff, and efficiency questions on one consistent network.





