AFTD Auto-Formalizing Theoretical Domains

simple_graph_maximal_packing_common_neighbors_le

theoremverified

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

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.

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

    lines 13–15

    uses three_set_two_star_cover_bound

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

    lines 16–17

    uses card_eq

      · intro s hs
        exact (hcl s hs).card_eq
  3. 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.

    lines 18–23

    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, ?_⟩
  4. 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.

    lines 24–32

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

        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]
  5. 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.

    lines 33–34

        obtain ⟨s, hs, hst⟩ := hmax T hT
        refine ⟨s, hs, ?_⟩
  6. 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.

    lines 35–43

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

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