Maximum matching

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

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Graph matching — A candidate must first be a valid matching.
• 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.