graph_matching_num_two_mul
Twice the matching number of G equals the supremum of twice the edge cardinalities of all matchings in G.
Statement
theorem graph_matching_num_two_mul {V : Type*} (G : SimpleGraph V) : 2 * graph_matching_num G = ⨆ (M : SimpleGraph.Subgraph G) (_ : M.IsMatching), 2 * M.edgeSet.encard
- Source
- step towards graph_matching_num_two_mul_le_card
- Verified
- 09 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- 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.
The proof, explained
The identity follows by unfolding the definition of the matching number as the supremum of edge cardinalities over all matchings in G. Since multiplication distributes over indexed suprema in the extended natural numbers ℕ∞ (ENat.mul_iSup), the factor of 2 distributes inside both suprema.
Twice the matching number of G equals the supremum of twice the edge cardinalities over all matchings in G.
We unfold the definition of graph_matching_num G as the supremum of edge cardinalities |E(M)| over all subgraphs M that satisfy the matching condition. Applying ENat.mul_iSup repeatedly distributes multiplication by 2 over both indexed suprema (first over subgraphs M, then over proofs that M is a matching), moving the factor 2 inside to multiply each cardinality directly.
uses
graph_matching_num,ENat.mul_iSupsimp_rw [graph_matching_num, ENat.mul_iSup]
graph_matching_num- The matching number of a graph G, defined as the supremum of the edge cardinalities of all matchings in G (with values in ℕ∞).
ENat.mul_iSup- Multiplication in ℕ∞ distributes over indexed suprema: a * (⨆ i, f i) = ⨆ i, (a * f i).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Twice the matching number of G equals the supremum of twice the edge cardinalities of all matchings in G. -/theorem graph_matching_num_two_mul {V : Type*} (G : SimpleGraph V) : 2 * graph_matching_num G = ⨆ (M : SimpleGraph.Subgraph G) (_ : M.IsMatching), 2 * M.edgeSet.encard := by simp_rw [graph_matching_num, ENat.mul_iSup]