Graph matching

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

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 — The complete vertices and edges are supplied.
• 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.