# Graph isomorphism

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

An isomorphism of finite simple graphs is a vertex bijection preserving both adjacency and nonadjacency for every pair.

mko-graph-isomorphism · definition · v0.10.0



## Mathematical statement

A graph isomorphism f:V(G)→V(H) must be bijective and, for all distinct u,v, {u,v} is an edge of G iff {f(u),f(v)} is an edge of H. Preserving edges without preserving nonedges is insufficient.





## Representative formula (exact TeX)

I(G,H)





## Assumptions


- Exercises supply the complete finite undirected simple-graph edge sets and a complete mapping table.
- A mismatch in an invariant such as the degree multiset can refute isomorphism; a match generally does not prove it.





## Symbol scope


- I — graph-isomorphism record
- G — source graph
- H — target graph





## Intuition, definition, and misconceptions

First check that the mapping is bijective.

Then check adjacency iff for every unordered pair of vertices.

Matching invariants provide necessary clues, not a general sufficient certificate.

Comparing degree sequences or checking only that original edges map to edges does not establish isomorphism.





## Adopted derivation guide

[Graph isomorphism: checking bijectivity and both directions of adjacency preservation from a complete mapping table](https://ocme.evemisslab.com/en/derivations/derivation-mko-graph-isomorphism-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite simple undirected graphs](https://ocme.evemisslab.com/en/mko/mko-graph/) — Isomorphisms act on complete finite simple graphs.
- [Bijectivity and unique preimages](https://ocme.evemisslab.com/en/mko/mko-bijective/) — The vertex map must be one-to-one and onto.
- [Binary relations and set projections](https://ocme.evemisslab.com/en/mko/mko-relation/) — Adjacency is a symmetric relation on vertices.





## Verification boundary

Only the specified complete finite simple graphs are classified.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add walks, paths, connected components and graph coloring.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/graph-isomorphism.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-graph-isomorphism/index.md)