simple_graph_maximum_triangle_packing_edge_meets
Every triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
Statement
theorem simple_graph_maximum_triangle_packing_edge_meets {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (hcl : ∀ t ∈ P, G.IsNClique 3 t) (hpair : (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (hsize : P.card = simple_graph_triangle_packing_number G) : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).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
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- Used by 11
- simple_graph_triangle_cover_of_full_common_matchingIf an edge common-neighbor graph has a matching as large as the graph triangle packing number, the triangle cover number is at most the…
- simple_graph_external_k4_private_pair_decreases_packingLet P be a maximum edge-disjoint triangle packing containing abc, and let a and b occur in no other triangle of P. If x lies outside the…
- simple_graph_triangle_outside_maximum_packing_card_le_oneEvery triangle in G shares an edge with any maximum packing, so it has at most one vertex outside the packing support.
- simple_graph_pair_stable_vertex_link_not_four_cycleIn a two-edge-stable graph, the graph induced by the neighborhood of any vertex cannot be exactly a four-cycle after isolated vertices are…
- simple_graph_pair_stable_support_max_outside_link_card_le_packingFor a support-maximal maximum triangle packing in a two-edge-stable graph, an outside vertex has at most one link edge per packed…
- simple_graph_pair_stable_private_k4_packing_incidenceLet a maximum packing in a two-edge-stable graph contain abc, with a and b private to that packing triangle. If abcx is a four-clique…
- 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…
- simple_graph_opposite_pair_stable_k4_attachmentLet P be a maximum edge-disjoint triangle packing containing abc, and let x complete abc to a four-clique. Suppose neither ax nor bx is an…
- simple_graph_maximum_packing_outside_triangles_inside_supportEvery triangle through a vertex outside a maximum triangle packing lies in that vertex together with the packing support.
- 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.
- simple_graph_pair_stable_vertex_link_edge_spoke_exchangeIn a two-edge-stable graph, for every edge yz of the link at x and every neighbor w of x, another link edge meets yz and avoids w.
The proof, explained
The theorem is proved by contradiction: if a triangle t does not share an edge with any triangle in a maximum packing P, then t shares at most one vertex with each member of P. This implies that t ∉ P and that P ∪ {t} is itself an edge-disjoint triangle packing. But then |P ∪ {t}| = |P| + 1, contradicting the maximality of |P|.
Suppose for contradiction that there exists a triangle t that shares at most one vertex with every triangle in P.
We introduce an arbitrary triangle t in G and assume the negation of the conclusion. Pushing negations through the existential quantifier yields the hypothesis that for every triangle s ∈ P, |s ∩ t| < 2 (that is, s and t share at most one vertex, so they are edge-disjoint).
classical intro t ht by_contra hno push_neg at hno
The triangle t is not already in P (t ∉ P).
If t were in P, our assumption would imply |t ∩ t| < 2. But t ∩ t = t and t is a 3-clique with 3 vertices, giving 3 < 2, a contradiction.
uses
Finset.inter_selfhave htP : t ∉ P := by intro htP have h := hno t htP rw [Finset.inter_self, ht.card_eq] at h omega
Every element of P ∪ {t} is a triangle in G.
Any element s ∈ P ∪ {t} is either t, which is a 3-clique by assumption, or an element of P, each of which is a 3-clique by the assumption that P is a triangle packing.
uses
Finset.mem_insert.mphave hp1 : ∀ s ∈ insert t P, G.IsNClique 3 s := by intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact ht · exact hcl s hs
The augmented family P ∪ {t} is pairwise edge-disjoint.
The triangles in P are already pairwise edge-disjoint. For any s ∈ P, the contradictory hypothesis gives |s ∩ t| < 2, so |s ∩ t| ≤ 1 and, by symmetry of intersection, |t ∩ s| ≤ 1. Therefore, every pair of distinct triangles in P ∪ {t} shares at most one vertex.
uses
Finset.coe_insert,Finset.inter_commhave hp2 : ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by rw [Finset.coe_insert] refine hpair.insert ?_ intro s hs _ have h := hno s hs exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩
The set A of sizes of all valid edge-disjoint triangle packings in G is bounded above.
We define A ⊆ ℕ as the set of cardinalities of all pairwise edge-disjoint collections of triangles. Since each such collection is a finite subset of the finite set of all vertex subsets (Finset V), its size is bounded by the total number of subsets of V.
uses
Finset.card_le_univlet A : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} have hbound : BddAbove A := by refine ⟨Fintype.card (Finset V), ?_⟩ rintro n ⟨T, _, _, rfl⟩ exact Finset.card_le_univ T
The cardinality |P ∪ {t}| is at most the triangle packing number of G.
Because P ∪ {t} is a valid edge-disjoint triangle packing, its cardinality belongs to A. Since A is bounded above, its supremum is by definition the triangle packing number of G, which must be at least |P ∪ {t}|.
uses
le_csSuphave hins : (insert t P).card ≤ simple_graph_triangle_packing_number G := by exact le_csSup hbound ⟨insert t P, hp1, hp2, rfl⟩
A contradiction is reached: |P| + 1 ≤ |P|.
Since t ∉ P, we have |P ∪ {t}| = |P| + 1. Substituting the hypothesis that |P| equals the triangle packing number into the inequality from the previous step yields |P| + 1 ≤ |P|, which is impossible.
uses
Finset.card_insert_of_notMemrw [Finset.card_insert_of_notMem htP, hsize] at hins omega
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, then it equals a or belongs to s.
Finset.coe_insert- Coercing an inserted finite set to a set equals inserting the element into the coerced set.
Finset.inter_comm- Intersection of finite sets is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
Finset.card_le_univ- The cardinality of any finite subset of a finite type is at most the cardinality of the whole type.
le_csSup- If a set in a conditionally complete lattice is bounded above, any element of the set is bounded by the supremum of the set.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases the set's cardinality by 1.
- In standard mathematics, the triangle packing number is defined as the maximum size of an edge-disjoint packing over a finite graph. In Lean, it is defined using `sSup` over `ℕ`, which requires an explicit proof that the set of sizes is bounded above (`BddAbove A`) before invoking `le_csSup`.
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_maximum_triangle_packing_edge_meets {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (hcl : ∀ t ∈ P, G.IsNClique 3 t) (hpair : (P : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1)) (hsize : P.card = simple_graph_triangle_packing_number G) : ∀ t : Finset V, G.IsNClique 3 t → ∃ s ∈ P, 2 ≤ (s ∩ t).card := by classical intro t ht by_contra hno push_neg at hno have htP : t ∉ P := by intro htP have h := hno t htP rw [Finset.inter_self, ht.card_eq] at h omega have hp1 : ∀ s ∈ insert t P, G.IsNClique 3 s := by intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact ht · exact hcl s hs have hp2 : ((insert t P : Finset (Finset V)) : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by rw [Finset.coe_insert] refine hpair.insert ?_ intro s hs _ have h := hno s hs exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩ let A : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} have hbound : BddAbove A := by refine ⟨Fintype.card (Finset V), ?_⟩ rintro n ⟨T, _, _, rfl⟩ exact Finset.card_le_univ T have hins : (insert t P).card ≤ simple_graph_triangle_packing_number G := by exact le_csSup hbound ⟨insert t P, hp1, hp2, rfl⟩ rw [Finset.card_insert_of_notMem htP, hsize] at hins omega