graph_is_maximum_matching
def
A subgraph M of a simple graph G is a maximum matching if M is a matching and its edge cardinality equals the matching number of G.
Statement
def graph_is_maximum_matching {V : Type*} (G : SimpleGraph V) (M : G.Subgraph) : Prop
- Defined in
- arXiv:2610.27833, Section 1.1
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- graph_matching_numThe matching number of a graph G is the supremum of the cardinalities of the edge sets of all matchings in G.
- Used by 2
- residual_matching_num_single_edge_exchange_iff_criticalLet G be a finite simple graph on a finite vertex type V, M a maximum matching of G, u an M-free vertex, and vw an edge of M such that uv…
- graph_is_maximum_matching_botThe empty subgraph is a maximum matching of the empty graph.
Read back from the Lean
Given a type V, a simple graph G on V, and a subgraph M of G, graph_is_maximum_matching G M asserts that M is a matching in G (M.IsMatching) and the extended cardinality (Set.encard) of the edge set of M is equal to the matching number of G (graph_matching_num G).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A subgraph M of G is a maximum matching if M is a matching and |M| = ν(G). -/ def graph_is_maximum_matching {V : Type*} (G : SimpleGraph V) (M : G.Subgraph) : Prop := M.IsMatching ∧ M.edgeSet.encard = graph_matching_num G