Graph isomorphism

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

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 — Isomorphisms act on complete finite simple graphs.
• Bijectivity and unique preimages — The vertex map must be one-to-one and onto.
• Binary relations and set projections — 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.