# Graph matching

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

A matching in a finite graph is an edge subset whose edges share no endpoints; the empty matching is allowed.

mko-graph-matching · definition · v0.10.0



## Mathematical statement

On a complete finite undirected simple graph, check that every selected edge exists and that their endpoint sets are disjoint. Distinguish matching, maximal, maximum and perfect. A larger valid matching can disprove maximum cardinality, but one matching alone does not establish optimality.





## Representative formula (exact TeX)

M(G)





## Assumptions


- The finite undirected loop-free simple graph is complete.
- The matching is selected by normalized original edge indices.





## Symbol scope


- M — matching
- G — finite simple graph





## Intuition, definition, and misconceptions

Every selected edge must exist in the original graph.

Any two selected edges have disjoint endpoint sets.

Maximal means no additional edge can be added directly; maximum means globally largest cardinality, and the two notions differ.

No directly addable edge does not establish global maximum cardinality, and perfect must not be conflated with maximum.





## Adopted derivation guide

[Maximal versus maximum in P4](https://ocme.evemisslab.com/en/derivations/derivation-mko-graph-matching-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/) — The complete vertices and edges are supplied.
- [Subset](https://ocme.evemisslab.com/en/mko/mko-subset/) — A matching is a subset of the edge set.





## Verification boundary

Only the complete finite graph and supplied witnesses are checked; maximum cardinality is not claimed without a global certificate.

not_formalized

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





## Next obligation

Add maximum matching and Hall's theorem.





## 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-matching.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-graph-matching/index.md)