simple_graph_maximal_packing_common_neighbors_le
If a maximal edge-disjoint triangle packing avoids an edge, that edge has at most twice as many common neighbors as the packing has triangles.
Statement
theorem simple_graph_maximal_packing_common_neighbors_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v) (hcl : ∀ t ∈ P, G.IsNClique 3 t) (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card) (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s)) : ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card ≤ 2 * P.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- Built on 1
- three_set_two_star_cover_boundThree-element sets covering outside points through either of two fixed centers cover at most twice as many points as there are sets.
- Used by 1
- simple_graph_triangle_packing_decreases_of_high_codegreeDeleting an edge with more than twice the maximum triangle packing number common neighbors strictly decreases the packing number.
The proof, explained
The bound is proved by applying the combinatorial lemma three_set_two_star_cover_bound, which shows that a set N has size at most 2|P| if every element of N is covered alongside u or v by some 3-element set in P. For any common neighbor w of the edge uv, the triple T = {u, v, w} forms a triangle in G. By the maximality of the triangle packing P, T must share at least two vertices with some triangle s ∈ P; since P avoids the edge uv, those two shared vertices must include w together with either u or v.
To bound the number of common neighbors, it suffices to verify the hypotheses of three_set_two_star_cover_bound.
Let N be the set of common neighbors of u and v. By three_set_two_star_cover_bound, if every set in P has cardinality 3, and every vertex w ∈ N is distinct from u and v and is contained in some triangle of P alongside u or v, then |N| ≤ 2|P|.
uses
three_set_two_star_cover_boundclassical let N := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w) apply three_set_two_star_cover_bound P N u v
Every set in the packing P has cardinality 3.
By the hypothesis hcl, every s ∈ P is a 3-clique in G, so its cardinality is 3 by card_eq.
uses
card_eq· intro s hs exact (hcl s hs).card_eq
Any common neighbor w of u and v is distinct from both u and v.
Since w is adjacent to u and to v in a simple graph, and simple graphs have no loops, w cannot equal u or v. Similarly, u ≠ v because they are adjacent.
uses
Finset.mem_filter.mp,Ne.symm· intro w hw have hw' : G.Adj u w ∧ G.Adj v w := (Finset.mem_filter.mp hw).2 have huw : u ≠ w := G.ne_of_adj hw'.1 have hvw : v ≠ w := G.ne_of_adj hw'.2 have huvne : u ≠ v := G.ne_of_adj huv refine ⟨Ne.symm huw, Ne.symm hvw, ?_⟩
The vertex set T = {u, v, w} forms a triangle (a 3-clique) in G.
The vertices u, v, and w are pairwise distinct and every pair is adjacent (u ~ v by huv, and u ~ w, v ~ w because w is a common neighbor). Hence {u, v, w} is a clique of size 3.
uses
SimpleGraph.isNClique_iff,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,Ne.symmlet 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 hw'.1 | exact hw'.1.symm | exact hw'.2 | exact hw'.2.symm · simp [T, huvne, huw, hvw, Ne.symm]
There exists a triangle s in P sharing at least two vertices with T.
By the maximality hypothesis hmax, any triangle in G must share at least an edge (at least 2 vertices) with some triangle s in the packing P.
obtain ⟨s, hs, hst⟩ := hmax T hT refine ⟨s, hs, ?_⟩
The triangle s contains w and at least one of u or v. automation
Because |s ∩ {u, v, w}| ≥ 2, the intersection contains two distinct vertices a and b. By hypothesis havoid, s cannot contain both u and v. Thus the two shared vertices cannot be {u, v}, leaving only {u, w} and {v, w}. In either case, w ∈ s and at least one of u, v is in s. Automated case analysis and simplification closes all cases.
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 have hbad := havoid s hs rcases hat with rfl | rfl | rfl <;> rcases hbt with rfl | rfl | rfl <;> simp_all
three_set_two_star_cover_bound- If P is a family of 3-element sets and N is a set of elements distinct from u and v such that every element of N belongs to some member of P containing u or v, then |N| ≤ 2|P|.
card_eq- An n-clique in a graph has exactly n vertices.
Finset.mem_filter.mp- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
SimpleGraph.isNClique_iff- A set of vertices is an n-clique if and only if every pair of distinct vertices is adjacent and the set has cardinality n.
Finset.mem_coe- Membership in the coercion of a finite set is equivalent to membership in the finite set.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.one_lt_card.mp- A finite set has cardinality at least 2 (greater than 1) if and only if it contains at least two distinct elements.
Finset.mem_inter.mp- An element belongs to the intersection of two sets if and only if it belongs to both sets.
- The proof reduces the graph-theoretic statement to an auxiliary combinatorial lemma in the knowledge base, three_set_two_star_cover_bound, which bounds a set covered by pairs from a 3-uniform hypergraph.
- In the final step, automated simplification (simp_all) exhausts all pairings between the two triangles to rule out the forbidden edge {u, v} and verify that the common neighbor w is covered alongside u or v.
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_maximal_packing_common_neighbors_le {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V) (P : Finset (Finset V)) (huv : G.Adj u v) (hcl : ∀ t ∈ P, G.IsNClique 3 t) (hmax : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card) (havoid : ∀ s ∈ P, ¬(u ∈ s ∧ v ∈ s)) : ((Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w)).card ≤ 2 * P.card := by classical let N := (Finset.univ : Finset V).filter (fun w => G.Adj u w ∧ G.Adj v w) apply three_set_two_star_cover_bound P N u v · intro s hs exact (hcl s hs).card_eq · intro w hw have hw' : G.Adj u w ∧ G.Adj v w := (Finset.mem_filter.mp hw).2 have huw : u ≠ w := G.ne_of_adj hw'.1 have hvw : v ≠ w := G.ne_of_adj hw'.2 have huvne : u ≠ v := G.ne_of_adj huv refine ⟨Ne.symm huw, Ne.symm hvw, ?_⟩ 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 hw'.1 | exact hw'.1.symm | exact hw'.2 | exact hw'.2.symm · simp [T, huvne, huw, hvw, 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