simple_graph_triangle_packing_insert_separated
A triangle sharing at most one vertex with every member of an edge-disjoint triangle packing can be inserted, increasing the packing size by one.
Statement
theorem simple_graph_triangle_packing_insert_separated {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (t : Finset V) (hp : ∀ s ∈ P, G.IsNClique 3 s) (hpp : (P : Set (Finset V)).Pairwise (fun s r => (s ∩ r).card ≤ 1)) (ht : G.IsNClique 3 t) (hsep : ∀ s ∈ P, (s ∩ t).card ≤ 1) : (∀ s ∈ insert t P, G.IsNClique 3 s) ∧ ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s r => (s ∩ r).card ≤ 1) ∧ (insert t P).card = P.card + 1
- 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 1
- simple_graph_triangle_cover_of_near_full_common_matchingIf an edge has a common-neighbor matching of size one below the graph triangle packing number and another common neighbor outside the…
The proof, explained
To add a triangle t sharing at most one vertex with every member of an edge-disjoint triangle packing P, the proof first establishes that t ∉ P: otherwise t would intersect itself in all 3 of its vertices, violating the separation hypothesis. The theorem then splits into three claims: every element of insert t P is a 3-clique, the elements remain pairwise edge-disjoint by the separation hypothesis and commutativity of intersection, and the packing cardinality increases by 1 because t ∉ P.
The triangle t does not already belong to P (t ∉ P).
Suppose for contradiction that t ∈ P. By the separation hypothesis hsep, t shares at most one vertex with every triangle in P, so |t ∩ t| ≤ 1. But t ∩ t = t by Finset.inter_self, and since t is a 3-clique, its cardinality is 3. This gives 3 ≤ 1, an arithmetic contradiction. Hence t ∉ P.
uses
Finset.inter_selfclassical have hnot : t ∉ P := by intro h have hh := hsep t h rw [Finset.inter_self, ht.card_eq] at hh omega
Every element of insert t P is a 3-clique in G.
We split the three-way conjunction into its constituent parts. For the first part, let s ∈ insert t P. By Finset.mem_insert.mp, either s = t or s ∈ P. If s = t, it is a 3-clique by the hypothesis ht; if s ∈ P, it is a 3-clique by the assumption hp on members of P.
uses
Finset.mem_insert.mprefine ⟨?_, ?_, ?_⟩ · intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact ht · exact hp s hs
The collection insert t P is pairwise edge-disjoint, sharing at most one vertex between any two distinct members.
We rewrite the finset insertion as a set insertion on coerced sets using Finset.coe_insert. Because P is already pairwise edge-disjoint (hpp), it suffices to show that t shares at most one vertex with every s ∈ P. The separation hypothesis hsep guarantees |s ∩ t| ≤ 1, and commutativity of intersection (Finset.inter_comm) ensures |t ∩ s| ≤ 1 as well.
uses
Finset.coe_insert,Finset.inter_comm· rw [Finset.coe_insert] refine hpp.insert ?_ intro s hs _ have hh := hsep s hs exact ⟨by rw [Finset.inter_comm]; exact hh, hh⟩
The size of insert t P is |P| + 1.
Because t ∉ P (established as hnot), inserting t into the finite set P increases its cardinality by 1: |insert t P| = 1 + |P| = |P| + 1, where addition is rearranged using Nat.add_comm.
uses
Nat.add_comm· simp [hnot, Nat.add_comm]
Finset.inter_self- The intersection of any finite set with itself is the set itself: s ∩ s = s.
Finset.mem_insert.mp- If an element belongs to the insertion of an element a into a finite set s, it is either equal to a or belongs to s.
Finset.coe_insert- The set coercion of an element inserted into a finite set equals the set insertion into the coerced set.
Finset.inter_comm- Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
Nat.add_comm- Addition of natural numbers is commutative: n + m = m + n.
- In a simple graph, two triangles (3-cliques) share at most one vertex if and only if they share no edges; hence the condition |s ∩ r| ≤ 1 formalizes edge-disjointness of triangles.
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_triangle_packing_insert_separated {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (t : Finset V) (hp : ∀ s ∈ P, G.IsNClique 3 s) (hpp : (P : Set (Finset V)).Pairwise (fun s r => (s ∩ r).card ≤ 1)) (ht : G.IsNClique 3 t) (hsep : ∀ s ∈ P, (s ∩ t).card ≤ 1) : (∀ s ∈ insert t P, G.IsNClique 3 s) ∧ ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s r => (s ∩ r).card ≤ 1) ∧ (insert t P).card = P.card + 1 := by classical have hnot : t ∉ P := by intro h have hh := hsep t h rw [Finset.inter_self, ht.card_eq] at hh omega refine ⟨?_, ?_, ?_⟩ · intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact ht · exact hp s hs · rw [Finset.coe_insert] refine hpp.insert ?_ intro s hs _ have hh := hsep s hs exact ⟨by rw [Finset.inter_comm]; exact hh, hh⟩ · simp [hnot, Nat.add_comm]