AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_edge_disjoint_perfect_matchings_le

theoremverified

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

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.

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

    line 6

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

    line 7

    uses Fin.castLE

      refine ⟨fun i => M (Fin.castLE hkm i), fun i => hperf _, ?_⟩
  3. 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.

    lines 8–9

    uses Fin.castLE_injective

      intro 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

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