AFTD Auto-Formalizing Theoretical Domains

graph_matching_num_two_mul

theoremverified

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.

  1. 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.

    line 4

    uses graph_matching_num, ENat.mul_iSup

      simp_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

/-- 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]
See it in the graphDiscuss this resultChallenge it