AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_edge_disjoint_perfect_matchings

deforiginal

A 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 which is a perfect matching, whose edge sets are pairwise disjoint.

Statement

def simple_graph_has_edge_disjoint_perfect_matchings {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
Related work
folklore
Verified
29 Oct 2026
Axioms
none listed
Used by 5

Read back from the Lean

Given a vertex type V, a simple graph G on V, and a natural number k, this defines the proposition that there exists a family of k subgraphs of G, M : Fin k → G.Subgraph, such that: 1. For every i : Fin k, the subgraph M i is a perfect matching of G. 2. The subgraphs are pairwise edge-disjoint: for all i, j : Fin k with i ≠ j, (M i).edgeSet and (M j).edgeSet are disjoint.

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 simple graph G contains at least k pairwise edge-disjoint perfect matchings. -/
def simple_graph_has_edge_disjoint_perfect_matchings {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop := ∃ (M : Fin k → G.Subgraph), (∀ i, (M i).IsPerfectMatching) ∧ Pairwise (fun i j => Disjoint (M i).edgeSet (M j).edgeSet)
See it in the graphDiscuss this resultChallenge it