simple_graph_common_neighbor_meets_packing_star
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
- simple_graph_common_neighbors_matching_of_avoided_packingFor a triangle-maximal family of size p avoiding an edge with d common neighbors, their induced graph contains a matching of size at least…
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).
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}.
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}
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.
uses
SimpleGraph.isNClique_iff,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,Ne.symmhave 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]
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.
obtain ⟨s, hs, hst⟩ := hmax T hT refine ⟨s, hs, ?_⟩
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}.
uses
Finset.one_lt_card.mp,Finset.mem_inter.mp,Finset.mem_insert,Finset.mem_singletonobtain ⟨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
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.
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
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.
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