simple_graph_has_edge_disjoint_perfect_matchings_le
If 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 perfect matchings.
Statement
theorem simple_graph_has_edge_disjoint_perfect_matchings_le {V : Type*} (G : SimpleGraph V) {k m : ℕ} (hkm : m ≤ k) (h : simple_graph_has_edge_disjoint_perfect_matchings G k) : simple_graph_has_edge_disjoint_perfect_matchings G m
- Source
- step towards op_652_half_degree_packing_negation
- Verified
- 30 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…
The proof, explained
The hypothesis provides a family of k pairwise edge-disjoint perfect matchings of G. Since m ≤ k, we restrict this family to its first m matchings via the canonical embedding Fin m ↪ Fin k. Every selected subgraph remains a perfect matching, and they remain pairwise edge-disjoint because the embedding is injective.
Extract a family M of k pairwise edge-disjoint perfect matchings of G.
By definition, G having at least k edge-disjoint perfect matchings means there is a family M : Fin k → G.Subgraph of perfect matchings whose edge sets are pairwise disjoint. We unpack this existential assumption into the family M, the proof hperf that each M(i) is a perfect matching, and the proof hdisj that distinct matchings have disjoint edge sets.
rcases h with ⟨M, hperf, hdisj⟩
Construct a family of m perfect matchings by restricting M to the first m indices.
Using the canonical inclusion Fin.castLE hkm : Fin m → Fin k, we index the first m matchings of M by i ↦ M (Fin.castLE hkm i). Each member of this family is a perfect matching because M (Fin.castLE hkm i) is in the range of M, so hperf applies immediately. This leaves only their pairwise disjointness to be verified.
uses
Fin.castLErefine ⟨fun i => M (Fin.castLE hkm i), fun i => hperf _, ?_⟩
The m perfect matchings are pairwise edge-disjoint.
Let i, j ∈ Fin m be distinct indices (i ≠ j). By the injectivity of the canonical embedding (Fin.castLE_injective), their images in Fin k are also distinct. Applying the pairwise disjointness hypothesis hdisj of the original family shows that the edge sets of M (Fin.castLE hkm i) and M (Fin.castLE hkm j) are disjoint.
uses
Fin.castLE_injectiveintro i j hij exact hdisj fun hc => hij (Fin.castLE_injective hkm hc)
Fin.castLE- Given n ≤ m, the canonical embedding of the finite type Fin n into Fin m preserving the underlying natural number value.
Fin.castLE_injective- The canonical embedding Fin.castLE from Fin n into Fin m is injective.
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 edge-disjoint perfect matchings, it also has at least m for any m ≤ k. -/theorem simple_graph_has_edge_disjoint_perfect_matchings_le {V : Type*} (G : SimpleGraph V) {k m : ℕ} (hkm : m ≤ k) (h : simple_graph_has_edge_disjoint_perfect_matchings G k) : simple_graph_has_edge_disjoint_perfect_matchings G m := by rcases h with ⟨M, hperf, hdisj⟩ refine ⟨fun i => M (Fin.castLE hkm i), fun i => hperf _, ?_⟩ intro i j hij exact hdisj fun hc => hij (Fin.castLE_injective hkm hc)