AFTD Auto-Formalizing Theoretical Domains

simple_graph_common_neighbor_meets_packing_star

theoremverified

For a triangle-maximal family avoiding an edge, each common neighbor of the edge lies with one endpoint in a family triangle.

Statement

theorem simple_graph_common_neighbor_meets_packing_star
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v)
    (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card)
    (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s)) :
    ∀ w : V, G.Adj u w → G.Adj v w → ∃ s ∈ P, w ∈ s ∧ (u ∈ s ∨ v ∈ s)
Source
Structural helper for the triangle packing-cover campaign, related to matching-cover reductions in https://arxiv.org/abs/2610.15269; see state/campaigns/triangle_reductions/high_codegree_route_in512.md.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

Given a common neighbor w of the edge {u, v}, the vertices {u, v, w} form a 3-clique T in the graph G. By the triangle-maximality condition on the family P, some set s ∈ P shares at least two vertices with T. Since P avoids the edge {u, v}, the set s cannot contain both u and v simultaneously. Therefore, the shared vertices must include w together with at least one of u or v, yielding w ∈ s and (u ∈ s ∨ v ∈ s).

  1. Let w be a common neighbor of u and v, and define T = {u, v, w} as a set of three pairwise distinct vertices.

    We introduce a vertex w adjacent to both u and v. Since a simple graph has no loops, an edge only connects distinct vertices, so u ≠ w, v ≠ w, and u ≠ v. We then define T to be the set {u, v, w}.

    lines 11–16

      classical
      intro w huw hvw
      have huwne : u ≠ w := G.ne_of_adj huw
      have hvwne : v ≠ w := G.ne_of_adj hvw
      have huvne : u ≠ v := G.ne_of_adj huv
      let T : Finset V := {u,v,w}
  2. T = {u, v, w} is a 3-clique in G.

    By SimpleGraph.isNClique_iff, a 3-clique is a clique of size 3. For any two distinct vertices x, y ∈ T, the pair {x, y} is one of {u, v}, {u, w}, or {v, w}, all of which are edges of G by hypothesis and symmetry. Moreover, since u, v, and w are pairwise distinct, T has cardinality 3.

    lines 17–24

    uses SimpleGraph.isNClique_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, Ne.symm

      have hT : G.IsNClique 3 T := by
        rw [SimpleGraph.isNClique_iff]
        constructor
        · intro x hx y hy hxy
          simp only [T, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hx hy
          rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl
          all_goals first | exact (hxy rfl).elim | exact huv | exact huv.symm | exact huw | exact huw.symm | exact hvw | exact hvw.symm
        · simp [T, huvne, huwne, hvwne, Ne.symm]
  3. There exists s ∈ P sharing at least two vertices with T, and it suffices to show that w ∈ s and (u ∈ s ∨ v ∈ s).

    By the maximality hypothesis hmax applied to the 3-clique T, there is some set s ∈ P that intersects T in at least two vertices. We choose this s as our witness.

    lines 25–26

      obtain ⟨s, hs, hst⟩ := hmax T hT
      refine ⟨s, hs, ?_⟩
  4. There exist two distinct elements a, b ∈ s that both belong to {u, v, w}.

    Because |s ∩ T| ≥ 2 > 1, Finset.one_lt_card.mp gives two distinct elements a, b ∈ s ∩ T. By Finset.mem_inter.mp, both vertices belong to s and both belong to T = {u, v, w}.

    lines 27–32

    uses Finset.one_lt_card.mp, Finset.mem_inter.mp, Finset.mem_insert, Finset.mem_singleton

      obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hst
      have has := (Finset.mem_inter.mp ha).1
      have hbs := (Finset.mem_inter.mp hb).1
      have hat := (Finset.mem_inter.mp ha).2
      have hbt := (Finset.mem_inter.mp hb).2
      simp only [T, Finset.mem_insert, Finset.mem_singleton] at hat hbt
  5. w ∈ s and (u ∈ s ∨ v ∈ s).

    By havoid, s cannot contain both u and v. We check all possible identities for the distinct vertices a, b ∈ {u, v, w}. Cases where a = b are impossible since a ≠ b, and {a, b} cannot be {u, v} because that would mean u, v ∈ s. In all remaining cases, one of the two vertices is w and the other is u or v, so w ∈ s and at least one of u or v belongs to s.

    lines 33–34

      have hbad := havoid s hs
      rcases hat with rfl | rfl | rfl <;> rcases hbt with rfl | rfl | rfl <;> simp_all
SimpleGraph.isNClique_iff
A vertex subset s is an n-clique of a simple graph if and only if every pair of distinct vertices in s is adjacent and s has cardinality n.
Finset.mem_coe
An element belongs to the set coercion ↑s of a finite set s if and only if it belongs to s.
Finset.mem_insert
An element x belongs to insert b s if and only if x = b or x ∈ s.
Finset.mem_singleton
An element b belongs to the singleton {a} if and only if b = a.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.one_lt_card.mp
If the cardinality of a finite set is greater than 1, then the set contains at least two distinct elements.
Finset.mem_inter.mp
If an element belongs to the intersection s₁ ∩ s₂, then it belongs to both s₁ and s₂.

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_common_neighbor_meets_packing_star    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v)    (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card)    (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s)) :    ∀ w : V, G.Adj u w → G.Adj v w → ∃ s ∈ P, w ∈ s ∧ (u ∈ s ∨ v ∈ s) := by  classical  intro w huw hvw  have huwne : u ≠ w := G.ne_of_adj huw  have hvwne : v ≠ w := G.ne_of_adj hvw  have huvne : u ≠ v := G.ne_of_adj huv  let T : Finset V := {u,v,w}  have hT : G.IsNClique 3 T := by    rw [SimpleGraph.isNClique_iff]    constructor    · intro x hx y hy hxy      simp only [T, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hx hy      rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl      all_goals first | exact (hxy rfl).elim | exact huv | exact huv.symm | exact huw | exact huw.symm | exact hvw | exact hvw.symm    · simp [T, huvne, huwne, hvwne, Ne.symm]  obtain ⟨s, hs, hst⟩ := hmax T hT  refine ⟨s, hs, ?_⟩  obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hst  have has := (Finset.mem_inter.mp ha).1  have hbs := (Finset.mem_inter.mp hb).1  have hat := (Finset.mem_inter.mp ha).2  have hbt := (Finset.mem_inter.mp hb).2  simp only [T, Finset.mem_insert, Finset.mem_singleton] at hat hbt  have hbad := havoid s hs  rcases hat with rfl | rfl | rfl <;> rcases hbt with rfl | rfl | rfl <;> simp_all
See it in the graphDiscuss this resultChallenge it