Introduction

Here are two friendship networks drawn on a page. They look different — the dots sit in different places, the lines cross differently. But are they actually the same network, just with the names shuffled and the layout rearranged?

That's graph isomorphism: deciding whether two graphs are identical in structure after you relabel the nodes. If you can pair up every dot in one with a dot in the other so that connections line up exactly, they're isomorphic — the same graph in disguise.

For tiny graphs you can eyeball it. But the obvious method — try every possible relabeling — runs into n! permutations and collapses fast. What makes this problem famous isn't just that brute force fails; it's where it sits in the complexity landscape, in a strange and rare in-between zone we'll explore.

Match the Graphs

Try it. The two graphs below are drawn very differently — but they are the same graph relabeled. Click a node on the left, then a node on the right to pair them. Build a full mapping, then Check whether every edge lines up.

<p class="hint">These two graphs are the <b>same graph relabeled</b>. Click a node on the <b>left</b>, then its match on the <b>right</b>, to pair them. Build a full mapping, then <b>Check</b> whether every edge lines up.</p>
<div class="boards">
  <div><div class="cap">Graph A</div><svg id="ga" viewBox="0 0 180 180"></svg></div>
  <div><div class="cap">Graph B</div><svg id="gb" viewBox="0 0 180 180"></svg></div>
</div>
<div id="map" class="maprow"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="check" type="button">Check</button>
  <button id="solve" type="button">Auto-solve</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.boards { display: grid; grid-template-columns: 1fr 1fr; gap: .6rem; }
.cap { font: 700 13px system-ui; color: #1d3557; text-align: center; margin-bottom: .2rem; }
svg { width: 100%; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.edge { stroke: #b8c4cf; stroke-width: 2.5; }
.node { fill: #8aa0b3; cursor: pointer; transition: fill .1s; }
.node:hover { fill: #457b9d; }
.node.sel { fill: #e76f51; }
.node.mapped { fill: #2a9d8f; }
.nlbl { font: 700 12px ui-monospace, monospace; fill: #fff; pointer-events: none; text-anchor: middle; dominant-baseline: central; }
.maprow { display: flex; flex-wrap: wrap; gap: .35rem; margin: .7rem 0 .4rem; min-height: 1.6rem; }
.pair { font: 700 12px ui-monospace, monospace; background: #e6f6ec; color: #0a7d33; border: 1px solid #b6e3c5; border-radius: 6px; padding: .15rem .45rem; }
.status { font-weight: 800; min-height: 1.3em; margin-bottom: .5rem; }
.status.ok { color: #0a7d33; } .status.bad { color: #c0392b; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Graph isomorphism: are two graphs the same after relabeling? The user
// builds a node mapping A->B; Check verifies every A-edge maps to a B-edge.
// Auto-solve brute-forces the 5! = 120 permutations.
const N = 5;
// Graph A: 5-cycle + one chord
const EA = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0], [0, 2]];
// B is A relabeled by P (A-node i becomes B-node P[i]) and redrawn
const P = [2, 0, 3, 4, 1];
const EB = EA.map(([u, v]) => [P[u], P[v]]);
const PA = pentagon(90, 90, 65);
const PB = [[40, 40], [150, 60], [90, 160], [30, 130], [160, 150]]; // scattered
const adjB = new Set(EB.map(([u, v]) => key(u, v)));

function pentagon(cx, cy, r) { const p = []; for (let i = 0; i < N; i++) { const a = -Math.PI / 2 + i * 2 * Math.PI / N; p.push([cx + r * Math.cos(a), cy + r * Math.sin(a)]); } return p; }
function key(u, v) { return u < v ? u + '-' + v : v + '-' + u; }

let map = {}; // A-node -> B-node
let selA = -1;

function drawGraph(svgId, pos, edges, side) {
  let s = '';
  edges.forEach(([u, v]) => { s += '<line class="edge" x1="' + pos[u][0] + '" y1="' + pos[u][1] + '" x2="' + pos[v][0] + '" y2="' + pos[v][1] + '"/>'; });
  for (let i = 0; i < N; i++) {
    let cls = 'node';
    if (side === 'A') { if (selA === i) cls += ' sel'; else if (map[i] !== undefined) cls += ' mapped'; }
    else { if (Object.values(map).includes(i)) cls += ' mapped'; }
    const label = side === 'A' ? 'a' + i : 'b' + i;
    s += '<circle class="' + cls + '" cx="' + pos[i][0] + '" cy="' + pos[i][1] + '" r="15" data-i="' + i + '"/>';
    s += '<text class="nlbl" x="' + pos[i][0] + '" y="' + pos[i][1] + '">' + label + '</text>';
  }
  const svg = document.getElementById(svgId);
  svg.innerHTML = s;
  svg.querySelectorAll('.node').forEach(n => n.addEventListener('click', () => click(side, +n.dataset.i)));
}

function click(side, i) {
  if (side === 'A') { selA = (selA === i ? -1 : i); }
  else if (selA >= 0) {
    // remove any existing A-node pointing to this B-node
    for (const k in map) if (map[k] === i) delete map[k];
    map[selA] = i; selA = -1;
  }
  render();
}

function render() {
  drawGraph('ga', PA, EA, 'A'); drawGraph('gb', PB, EB, 'B');
  document.getElementById('map').innerHTML = Object.keys(map).sort()
    .map(a => '<span class="pair">a' + a + ' → b' + map[a] + '</span>').join('');
}

function check() {
  const st = document.getElementById('status');
  if (Object.keys(map).length < N || new Set(Object.values(map)).size < N) {
    st.className = 'status bad'; st.textContent = 'Map all five nodes one-to-one first.'; return;
  }
  const bad = EA.find(([u, v]) => !adjB.has(key(map[u], map[v])));
  if (bad) { st.className = 'status bad'; st.textContent = fmt('✗ Edge a%v%–a%v2% has no match. Not an isomorphism — yet.', { v: bad[0], v2: bad[1] }); }
  else { st.className = 'status ok'; st.textContent = '✓ Every edge lines up — the graphs are isomorphic!'; }
}

function* perms(arr) { if (arr.length <= 1) { yield arr; return; } for (let i = 0; i < arr.length; i++) { const rest = arr.slice(0, i).concat(arr.slice(i + 1)); for (const p of perms(rest)) yield [arr[i], ...p]; } }
function solve() {
  for (const p of perms([0, 1, 2, 3, 4])) {
    if (EA.every(([u, v]) => adjB.has(key(p[u], p[v])))) {
      map = {}; p.forEach((b, a) => map[a] = b); selA = -1; render();
      document.getElementById('status').className = 'status ok';
      document.getElementById('status').textContent = '✓ Found a valid relabeling — the graphs are isomorphic.';
      return;
    }
  }
}

document.getElementById('check').addEventListener('click', check);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', () => { map = {}; selA = -1; document.getElementById('status').textContent = ''; render(); });
render();
Result
Console

Get one wrong and an edge won't match. Stuck? Auto-solve searches the relabelings for you. With just five nodes that's quick — but imagine the search over hundreds of nodes, and you feel why this needs cleverness, not brute force.

The In-Between

Graph isomorphism is one of the most fascinating residents of complexity theory because of where it doesn't fit:

  • Checking a claimed mapping is trivial: verify each edge of one graph maps to an edge of the other.
  • Brute force tries all n! relabelings — hopeless beyond small graphs.
  • It's in NP, like the hard problems here. But unlike them, nobody has proven it NP-complete — and nobody has found a polynomial algorithm either.
  • A rare limbo. If P ≠ NP, there must exist problems that are neither in P nor NP-complete (NP-intermediate), and graph isomorphism is the most famous candidate. It seems to float between the two worlds.
  • Babai's breakthrough. In 2015 László Babai gave a quasi-polynomial algorithm — dramatically faster than exponential, tantalizingly close to polynomial. It didn't settle the question, but it shifted the landscape.
  • In practice it's easy. Tools like nauty decide isomorphism for huge real-world graphs in a blink; the hard cases are rare and contrived.

So this problem teaches a subtle lesson: "hard" isn't binary. Some problems live in a gray zone that the P-versus-NP map doesn't neatly capture.

Where It Matters

Recognizing the same structure under a disguise shows up everywhere:

  • Chemistry: deciding whether two molecular diagrams are the same compound — chemical databases dedupe and search by graph isomorphism.
  • Pattern and image recognition: matching shapes and scenes represented as graphs.
  • Network analysis: spotting repeated motifs or identical sub-networks.
  • Hardware verification: checking that a manufactured circuit matches its reference design.
  • Databases and knowledge graphs: query matching and deduplication.

Because practical solvers are so fast, isomorphism is a quiet workhorse — its theoretical mystery rarely bites in real applications.

Conclusion

Graph isomorphism is the misfit of this collection — and that's exactly why it matters. Most problems here are comfortably easy or comfortably NP-hard. This one refuses to commit: not proven hard, not proven easy, and pushed toward the easy side by Babai's beautiful quasi-polynomial result.

It's a reminder that the P-versus-NP picture, powerful as it is, has subtle territory in between. And it's a quietly hopeful story: a problem long feared intractable turns out to be solvable in a blink in practice, with its deepest theoretical question still gloriously open.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/graph-isomorphism/Content licensed under CC BY-NC 4.0.