AFTD Auto-Formalizing Theoretical Domains

simple_graph_matching_link_star_packing

theoremverified

Disjoint two-vertex edges in a vertex link yield a same-size edge-disjoint triangle packing through the vertex.

Statement

theorem simple_graph_matching_link_star_packing
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (z : V) (M : Finset (Finset V))
    (hM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj z x) ∧
      (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y))
    (hdis : (M : Set (Finset V)).Pairwise Disjoint) :
    (∀ t ∈ M.image (fun e => insert z e), G.IsNClique 3 t) ∧
    ((M.image (fun e => insert z e) : Finset (Finset V)) : Set (Finset V)).Pairwise
      (fun s t => (s ∩ t).card ≤ 1) ∧
    (M.image (fun e => insert z e)).card = M.card
Source
Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

The proof, explained

Given a collection M of pairwise disjoint edges in the link of a vertex z, we cone z over each edge e ∈ M to form triangles t = e ∪ {z}. Because z is adjacent to every vertex in each edge e and the vertices of e are adjacent to each other, with z ∉ e by graph irreflexivity, each such t is a 3-clique. Distinct triangles come from disjoint edges, so their intersection is contained in the singleton {z}, which means they share at most one vertex and are edge-disjoint. Finally, erasing z recovers the original edge e, proving the map e ↦ e ∪ {z} is injective and thus yields exactly |M| triangles.

  1. The center vertex z does not belong to any edge in M.

    Assuming for contradiction that z ∈ e for some e ∈ M, the hypothesis hM that every vertex in e is adjacent to z would imply that z is adjacent to itself (G.Adj z z). In a simple graph, adjacency is irreflexive (G.irrefl), which yields False.

    lines 15–19

      classical
      have hnz : ∀ e ∈ M, z ∉ e := by
        intro e he hz
        have hz' := (hM e he).2.1 z hz
        exact G.irrefl hz'
  2. Each set e ∪ {z} for e ∈ M is a 3-clique in G.

    We take an arbitrary triangle t in the image of M under coning with z, so t = e ∪ {z} for some e ∈ M (by Finset.mem_image.mp). By SimpleGraph.isNClique_iff, t is a 3-clique if it is a clique and has cardinality 3. For the clique condition, we check all pairs of distinct vertices a, b ∈ e ∪ {z} (using Finset.mem_coe and Finset.mem_insert): the case a = z = b contradicts a ≠ b; if one vertex is z and the other is in e, they are adjacent by hM; if both lie in e, they are distinct vertices in e and are adjacent by hM. For the cardinality, since z ∉ e, the size of e ∪ {z} is |e| + 1 = 2 + 1 = 3 by Finset.card_insert_of_notMem and hM.

    lines 20–32

    uses Finset.mem_image.mp, SimpleGraph.isNClique_iff, Finset.mem_coe, Finset.mem_insert, Finset.card_insert_of_notMem

      constructor
      · intro t ht
        obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp ht
        rw [SimpleGraph.isNClique_iff]
        constructor
        · intro a ha b hb hab
          simp only [Finset.mem_coe, Finset.mem_insert] at ha hb
          rcases ha with rfl | ha <;> rcases hb with rfl | hb
          · exact (hab rfl).elim
          · exact (hM e he).2.1 b hb
          · exact ((hM e he).2.1 a ha).symm
          · exact (hM e he).2.2 a ha b hb hab
        · rw [Finset.card_insert_of_notMem (hnz e he), (hM e he).1]
  3. Any two distinct triangles in the image share at most one vertex.

    Let s = e ∪ {z} and t = f ∪ {z} be distinct triangles for e, f ∈ M (by Finset.mem_image.mp). Since s ≠ t, the edges e and f must be distinct (via congrArg), so the pairwise disjointness of M implies e and f are disjoint. We then show (e ∪ {z}) ∩ (f ∪ {z}) ⊆ {z}: any x in the intersection (Finset.mem_inter, Finset.mem_insert) must either equal z (putting it in {z} by Finset.mem_singleton) or belong to both e and f, which contradicts their disjointness (Finset.disjoint_left.mp, False.elim). By monotonicity of cardinality (Finset.card_le_card), |s ∩ t| ≤ |{z}| = 1.

    lines 33–51

    uses Finset.mem_image.mp, congrArg, Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton, False.elim, Finset.disjoint_left.mp, Finset.card_le_card

      constructor
      · intro s hs t ht hst
        obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs
        obtain ⟨f, hf, rfl⟩ := Finset.mem_image.mp ht
        have hef : e ≠ f := by
          intro h
          apply hst
          exact congrArg (fun q : Finset V => insert z q) h
        have hefdis : Disjoint e f := hdis he hf hef
        have hsub : insert z e ∩ insert z f ⊆ {z} := by
          intro x hx
          simp only [Finset.mem_inter, Finset.mem_insert] at hx
          simp only [Finset.mem_singleton]
          rcases hx.1 with rfl | hxe
          · rfl
          · rcases hx.2 with rfl | hxf
            · rfl
            · exact False.elim (Finset.disjoint_left.mp hefdis hxe hxf)
        exact (Finset.card_le_card hsub).trans (by simp)
  4. The number of triangles equals |M|.

    By Finset.card_image_iff.mpr, it suffices to prove that the coning map e ↦ e ∪ {z} is injective on M. Given e, f ∈ M with e ∪ {z} = f ∪ {z}, erasing z from both sets (via congrArg) preserves equality. Because z ∉ e and z ∉ f, removing z leaves e and f unchanged, so e = f.

    lines 52–55

    uses Finset.card_image_iff.mpr, congrArg

      · apply Finset.card_image_iff.mpr
        intro e he f hf heq
        have hh := congrArg (fun s : Finset V => s.erase z) heq
        simpa [hnz e he, hnz f hf] using hh
False.elim
From a contradiction (False), any conclusion follows.
Finset.card_image_iff.mpr
If a function is injective on a finite set S, the cardinality of the image f(S) equals the cardinality of S.
Finset.card_insert_of_notMem
Inserting an element a into a finite set s increases its size by 1, provided a ∉ s.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.disjoint_left.mp
If two sets are disjoint, no element of the first belongs to the second.
Finset.mem_coe
An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_image.mp
If y belongs to f(S), there exists x ∈ S such that f(x) = y.
Finset.mem_insert
An element a belongs to s ∪ {b} if and only if a = b or a ∈ s.
Finset.mem_inter
An element belongs to s₁ ∩ s₂ if and only if it belongs to both s₁ and s₂.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
congrArg
Applying a function to equal inputs yields equal outputs.
SimpleGraph.isNClique_iff
A finite set of vertices forms an n-clique in G if and only if it has cardinality n and every pair of distinct vertices in it is adjacent.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_matching_link_star_packing    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (z : V) (M : Finset (Finset V))    (hM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj z x) ∧      (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y))    (hdis : (M : Set (Finset V)).Pairwise Disjoint) :    (∀ t ∈ M.image (fun e => insert z e), G.IsNClique 3 t) ∧    ((M.image (fun e => insert z e) : Finset (Finset V)) : Set (Finset V)).Pairwise      (fun s t => (s ∩ t).card ≤ 1) ∧    (M.image (fun e => insert z e)).card = M.card := by  classical  have hnz : ∀ e ∈ M, z ∉ e := by    intro e he hz    have hz' := (hM e he).2.1 z hz    exact G.irrefl hz'  constructor  · intro t ht    obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp ht    rw [SimpleGraph.isNClique_iff]    constructor    · intro a ha b hb hab      simp only [Finset.mem_coe, Finset.mem_insert] at ha hb      rcases ha with rfl | ha <;> rcases hb with rfl | hb      · exact (hab rfl).elim      · exact (hM e he).2.1 b hb      · exact ((hM e he).2.1 a ha).symm      · exact (hM e he).2.2 a ha b hb hab    · rw [Finset.card_insert_of_notMem (hnz e he), (hM e he).1]  constructor  · intro s hs t ht hst    obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs    obtain ⟨f, hf, rfl⟩ := Finset.mem_image.mp ht    have hef : e ≠ f := by      intro h      apply hst      exact congrArg (fun q : Finset V => insert z q) h    have hefdis : Disjoint e f := hdis he hf hef    have hsub : insert z e ∩ insert z f ⊆ {z} := by      intro x hx      simp only [Finset.mem_inter, Finset.mem_insert] at hx      simp only [Finset.mem_singleton]      rcases hx.1 with rfl | hxe      · rfl      · rcases hx.2 with rfl | hxf        · rfl        · exact False.elim (Finset.disjoint_left.mp hefdis hxe hxf)    exact (Finset.card_le_card hsub).trans (by simp)  · apply Finset.card_image_iff.mpr    intro e he f hf heq    have hh := congrArg (fun s : Finset V => s.erase z) heq    simpa [hnz e he, hnz f hf] using hh
See it in the graphDiscuss this resultChallenge it