Same Graph in Disguise?

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.

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">{{hint}}</p>
<div class="boards">
  <div><div class="cap">{{cap_a}}</div><svg id="ga" viewBox="0 0 180 180"></svg></div>
  <div><div class="cap">{{cap_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">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.

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.