# Maximum matching

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

A maximum matching has the greatest edge count among all valid matchings of the complete finite graph; it may be nonunique and need not be perfect.

mko-maximum-matching · definition · v0.10.0



## Mathematical statement

For small complete finite simple graphs, exhaustively enumerate all edge subsets, retain only valid matchings and obtain the exact maximum size and witnesses. Validate every candidate as a matching first. Maximal does not mean maximum, and several maximum matchings may coexist.





## Representative formula (exact TeX)

X(G)





## Assumptions


- The finite undirected loop-free simple graph is complete and its edge count meets the contract bound.
- A global conclusion needs the complete 2^|E| enumeration or an equivalent global upper bound.





## Symbol scope


- X — maximum matching
- G — finite simple graph





## Intuition, definition, and misconceptions

Check matching validity first.

Maximum cardinality uses a global comparison or upper bound.

Maximality, perfect coverage and uniqueness remain separate properties.

A directly unextendable maximal matching is not automatically maximum, perfect or unique.





## Adopted derivation guide

[All eight edge-subset candidates on a three-edge graph](https://ocme.evemisslab.com/en/derivations/derivation-mko-maximum-matching-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Graph matching](https://ocme.evemisslab.com/en/mko/mko-graph-matching/) — A candidate must first be a valid matching.
- [Optimization problem](https://ocme.evemisslab.com/en/mko/mko-optimization-problem/) — The objective is global maximum cardinality.





## Verification boundary

Only complete finite graphs with bounded edge count are handled.

not_formalized

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





## Next obligation

Add Hall's theorem and matching algorithms.





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