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
- simple_graph_has_perfect_matching_of_edge_disjointIf a simple graph G contains at least k pairwise edge-disjoint perfect matchings for some k > 0, then G contains a perfect matching.
- simple_graph_has_edge_disjoint_perfect_matchings_leIf a simple graph G has at least k pairwise edge-disjoint perfect matchings and m ≤ k, then G has at least m pairwise edge-disjoint…
- op_657_half_degree_packing_of_min_degree_le_twoFor every squarefree natural number n with at least two distinct prime factors and any positive coprime integers a and b, if the coprime…
- op_652_half_degree_packing_of_min_degree_le_twoFor any natural number n ≥ 2 and integers a, b with b > 0, if the coprime divisor progression graph B has minimum degree at most 2 and…
- op_652_half_degree_packing_of_primeFor any prime p and integers a, b with b > 0, if the coprime divisor progression graph B has a perfect matching, then B contains at least…
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)