simple_graph_exists_support_maximum_triangle_packing
Every finite graph has a maximum triangle packing whose vertex support has maximum cardinality among all maximum triangle packings.
Statement
theorem simple_graph_exists_support_maximum_triangle_packing (n : ℕ) (G : SimpleGraph (Fin n)) : ∃ P : Finset (Finset (Fin n)), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ ∀ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, G.IsNClique 3 t) → (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) → Q.card = P.card → (Q.biUnion id).card ≤ (P.biUnion id).card
- Source
- Finite support-maximal selection used in the general pair-stable forced-K4 reduction; no novelty claim.
- Verified
- 10 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).
The proof, explained
The triangle packing number of a finite graph is the maximum cardinality of an edge-disjoint collection of triangles. Because the graph is finite, the set of sizes of all triangle packings is non-empty and bounded above, guaranteeing the existence of a maximum packing. The collection of all maximum triangle packings is therefore a non-empty finite set, so we can select one that maximizes the cardinality of its vertex support.
The set A of sizes of all triangle packings of G is non-empty and bounded above.
We enable classical logic and define A ⊆ ℕ as the set of cardinalities of all triangle packings (families of 3-cliques pairwise intersecting in at most one vertex). The empty set is vacuously a triangle packing of size 0, so 0 ∈ A and A is non-empty. Since every packing is a family of vertex subsets of G, its cardinality is bounded by the total number of subsets of the vertex set, so A is bounded above.
uses
Finset.card_le_univclassical let A : Set ℕ := {k | ∃ P : Finset (Finset (Fin n)), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = k} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset (Fin n)), ?_⟩ rintro k ⟨P, _, _, rfl⟩ exact Finset.card_le_univ P
There exists a triangle packing P₀ achieving the graph's triangle packing number.
Since A is a non-empty, bounded-above set of natural numbers, its supremum belongs to A by Nat.sSup_mem. By definition, the triangle packing number of G is precisely sSup A, so there exists a packing P₀ whose cardinality equals this maximum packing number.
uses
Nat.sSup_memobtain ⟨P₀,h₀tri,h₀pair,h₀card⟩ := Nat.sSup_mem hne hbdd have h₀max : P₀.card = simple_graph_triangle_packing_number G := by change P₀.card = simple_graph_triangle_packing_number G at h₀card exact h₀card
The collection F of all maximum triangle packings is a non-empty finite set.
We define F as the subcollection of the finite universe of families of vertex subsets consisting of all triangle packings of size equal to the triangle packing number. Because P₀ satisfies all these conditions, P₀ ∈ F, which proves F is non-empty.
uses
Finset.mem_filter,Finset.mem_univ,true_andlet F : Finset (Finset (Finset (Fin n))) := Finset.univ.filter (fun P => (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G) have hF : F.Nonempty := by refine ⟨P₀, ?_⟩ simp only [F, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨h₀tri,h₀pair,h₀max⟩
There exists a maximum triangle packing P whose vertex support has maximum cardinality among all maximum triangle packings.
Because F is a non-empty finite set, Finset.exists_max_image implies that the function measuring the size of the vertex support, |⋃ P| = (P.biUnion id).card, achieves its maximum on F at some packing P. Expanding the definition of membership in F shows that P is an edge-disjoint collection of triangles of maximum cardinality.
uses
Finset.exists_max_image,Finset.mem_filter,Finset.mem_univ,true_andobtain ⟨P,hP,hmax⟩ := Finset.exists_max_image F (fun P => (P.biUnion id).card) hF have hP' : (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G := by simpa only [F, Finset.mem_filter, Finset.mem_univ, true_and] using hP
P is a maximum triangle packing whose vertex support has cardinality at least that of any other maximum packing.
We provide P as the witness. Its packing and maximality properties were established in the previous step. For any other triangle packing Q with |Q| = |P|, Q also achieves the maximum packing number and therefore belongs to F. By the maximality of P on F, the vertex support of Q has cardinality at most that of P.
uses
Finset.mem_filter,Finset.mem_univ,true_andrefine ⟨P,hP'.1,hP'.2.1,hP'.2.2, ?_⟩ intro Q hQtri hQpair hQcard apply hmax Q simp only [F, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hQtri,hQpair,hQcard.trans hP'.2.2⟩
Finset.card_le_univ- the cardinality of any finite subset of a finite type is at most the cardinality of the ambient type
Finset.exists_max_image- any function from a non-empty finite set into a linearly ordered type attains its maximum
Finset.mem_filter- an element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate
Finset.mem_univ- every element of a finite type belongs to the universal finset univ
Nat.sSup_mem- if a set of natural numbers is non-empty and bounded above, its supremum belongs to the set
true_and- conjunction with True simplifies to the proposition itself
- In this formalization, a triangle is represented as a 3-clique, edge-disjointness between two triangles is expressed as their intersection having cardinality at most 1, and the vertex support (the union of the vertices in the packing) is written as P.biUnion id.
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 scoped Sym2set_option maxRecDepth 10000set_option maxHeartbeats 3000000theorem simple_graph_exists_support_maximum_triangle_packing (n : ℕ) (G : SimpleGraph (Fin n)) : ∃ P : Finset (Finset (Fin n)), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G ∧ ∀ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, G.IsNClique 3 t) → (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) → Q.card = P.card → (Q.biUnion id).card ≤ (P.biUnion id).card := by classical let A : Set ℕ := {k | ∃ P : Finset (Finset (Fin n)), (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = k} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset (Fin n)), ?_⟩ rintro k ⟨P, _, _, rfl⟩ exact Finset.card_le_univ P obtain ⟨P₀,h₀tri,h₀pair,h₀card⟩ := Nat.sSup_mem hne hbdd have h₀max : P₀.card = simple_graph_triangle_packing_number G := by change P₀.card = simple_graph_triangle_packing_number G at h₀card exact h₀card let F : Finset (Finset (Finset (Fin n))) := Finset.univ.filter (fun P => (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G) have hF : F.Nonempty := by refine ⟨P₀, ?_⟩ simp only [F, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨h₀tri,h₀pair,h₀max⟩ obtain ⟨P,hP,hmax⟩ := Finset.exists_max_image F (fun P => (P.biUnion id).card) hF have hP' : (∀ t ∈ P, G.IsNClique 3 t) ∧ (P : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ P.card = simple_graph_triangle_packing_number G := by simpa only [F, Finset.mem_filter, Finset.mem_univ, true_and] using hP refine ⟨P,hP'.1,hP'.2.1,hP'.2.2, ?_⟩ intro Q hQtri hQpair hQcard apply hmax Q simp only [F, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hQtri,hQpair,hQcard.trans hP'.2.2⟩