AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_perfect_matching_of_edge_disjoint

theoremverified

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

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.

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

    line 5

      rcases h with ⟨M, hM, -⟩
  2. $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.

    line 6

      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

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