simple_graph_has_perfect_matching_of_edge_disjoint
If a simple graph G contains at least k pairwise edge-disjoint perfect matchings for some k > 0, then G contains a perfect matching.
Statement
theorem simple_graph_has_perfect_matching_of_edge_disjoint {V : Type*} (G : SimpleGraph V) {k : ℕ} (hk : 0 < k) (h : simple_graph_has_edge_disjoint_perfect_matchings G k) : ∃ M : G.Subgraph, M.IsPerfectMatching
- Source
- folklore
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_has_edge_disjoint_perfect_matchingsA simple graph G has at least k pairwise edge-disjoint perfect matchings if there exists an indexed family of k subgraphs of G, each of…
Read back from the Lean
For any type V, any simple graph G on V, and any natural number k strictly greater than 0: if G has k edge-disjoint perfect matchings (that is, there exists a family of subgraphs M : Fin k → G.Subgraph such that each M i is a perfect matching and for all i ≠ j in Fin k, the edge sets of M i and M j are disjoint), then there exists a subgraph M of G that is a perfect matching.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The hypothesis provides a family of $k$ edge-disjoint perfect matchings indexed by $\operatorname{Fin} k$. Because $k > 0$, the index set is nonempty, so taking the first matching (at index 0) immediately witnesses that $G$ has a perfect matching.
We obtain a family of subgraphs $M$ indexed by $\operatorname{Fin} k$, each of which is a perfect matching of $G$.
Unpack the assumption that $G$ has $k$ edge-disjoint perfect matchings into an indexed family of subgraphs $M : \operatorname{Fin} k \to G\text{.Subgraph}$ and the fact $hM$ that every $M_i$ is a perfect matching, discarding the disjointness condition.
rcases h with ⟨M, hM, -⟩
$G$ contains a perfect matching.
Since $k > 0$, the index $0$ is valid in $\operatorname{Fin} k$, given by $\langle 0, hk \rangle$. The matching $M_{\langle 0, hk \rangle}$ and the proof $hM \langle 0, hk \rangle$ that it is a perfect matching serve as the required witness.
exact ⟨M ⟨0, hk⟩, hM ⟨0, hk⟩⟩
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.
/-- If a graph has at least k pairwise edge-disjoint perfect matchings with k > 0, it has a perfect matching. -/theorem simple_graph_has_perfect_matching_of_edge_disjoint {V : Type*} (G : SimpleGraph V) {k : ℕ} (hk : 0 < k) (h : simple_graph_has_edge_disjoint_perfect_matchings G k) : ∃ M : G.Subgraph, M.IsPerfectMatching := by rcases h with ⟨M, hM, -⟩ exact ⟨M ⟨0, hk⟩, hM ⟨0, hk⟩⟩