simple_graph_support_max_packing_outside_swap_private
If P has maximum vertex support among triangle packings of its size, replacing packed triangle abc by abx with x outside P is possible only if c belongs to no other triangle of P.
Statement
theorem simple_graph_support_max_packing_outside_swap_private (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hsupport : ∀ 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) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hface : G.IsNClique 3 ({a,b,x} : Finset (Fin n))) : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → c ∉ q
- Source
- Support-maximal exchange reduction for the general pair-stable triangle-packing residual; 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).
- Used by 1
- simple_graph_support_max_packing_external_k4_decreases_packingIf a maximum triangle packing has maximum vertex support, a packed face abc and an outside fourth vertex x spanning a four-clique force…
The proof, explained
The theorem is proved by contradiction: suppose some other triangle q ∈ P \ {p} contains c. We consider the swapped packing Q = (P \ {p}) ∪ {t}, where p = {a, b, c} is replaced by t = {a, b, x}. Since x lies outside the vertex support of P, t shares at most one vertex with every other triangle in P, making Q a valid pairwise edge-disjoint triangle packing with |Q| = |P|. However, Q covers all vertices of P (since a, b ∈ t and c ∈ q) plus the new vertex x, strictly increasing the vertex support and contradicting the maximality of P.
The vertex x does not belong to any triangle in P, so in particular x ∉ p.
Define p = {a, b, c} and t = {a, b, x}. By hypothesis, x is not in the vertex support of P (the union of all triangles in P). Thus x cannot belong to any member q ∈ P, and since p ∈ P, x ∉ p.
uses
Finset.mem_biUnion.mprclassical let p : Finset (Fin n) := {a,b,c} let t : Finset (Fin n) := {a,b,x} have hp' : p ∈ P := hp have hxP : ∀ q ∈ P, x ∉ q := by intro q hq hqx apply hx exact Finset.mem_biUnion.mpr ⟨q,hq,hqx⟩ have hxp : x ∉ p := hxP p hp'
The vertices a and b are distinct (a ≠ b).
Assume for contradiction that a = b. Then p = {a, b, c} is a subset of the two-element set {a, c}, meaning |p| ≤ |{a, c}| ≤ 2. But p is a 3-clique in G, so |p| = 3, yielding 3 ≤ 2, a contradiction.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_le_twohave hab : a ≠ b := by intro h have hs : p ⊆ ({a,c} : Finset (Fin n)) := by intro v hv simp only [p, Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have htwo := Finset.card_le_two (a := a) (b := c) have hp3 := (htri p hp').card_eq omega
The candidate triangle t = {a, b, x} is not already an element of P.
If t ∈ P, then because x ∈ t, x would belong to a triangle in P, contradicting the fact that x is outside the vertex support of P.
have htP : t ∉ P := by intro ht have : x ∈ t := by simp [t] exact hxP t ht this
Every element of the swapped packing Q = (P \ {p}) ∪ {t} is a 3-clique in G.
Let R = P \ {p} and Q = {t} ∪ R. Any s ∈ Q is either t, which is a 3-clique by the hypothesis hface, or an element of R ⊆ P, which is a 3-clique by the assumption that every element of P is a 3-clique.
uses
Finset.mem_of_mem_erase,Finset.mem_insert.mplet R : Finset (Finset (Fin n)) := P.erase p let Q : Finset (Finset (Fin n)) := insert t R have hQt : t ∈ Q := by simp [Q] have hRsub : R ⊆ P := by intro q hq; exact Finset.mem_of_mem_erase hq have hface' : G.IsNClique 3 t := hface have hQtri : ∀ s ∈ Q, G.IsNClique 3 s := by intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact hface' · exact htri s (hRsub hs)
The triangle t intersects every other triangle q ∈ R in at most one vertex: |t ∩ q| ≤ 1.
For any q ∈ R = P \ {p}, q belongs to P and q ≠ p, so pairwise edge-disjointness gives |p ∩ q| ≤ 1. Any vertex v ∈ t ∩ q must be in t = {a, b, x} and in q. Since x cannot belong to any triangle in P, v ≠ x, which forces v ∈ {a, b} ⊆ p. Therefore t ∩ q ⊆ p ∩ q, and taking cardinalities gives |t ∩ q| ≤ |p ∩ q| ≤ 1.
uses
Finset.ne_of_mem_erase,Finset.mem_inter.mp,Finset.mem_insert,Finset.mem_singleton,Or.inl,Or.inr,False.elim,Finset.mem_inter.mpr,Finset.card_le_cardhave htpair : ∀ q ∈ R, (t ∩ q).card ≤ 1 := by intro q hq have hqP : q ∈ P := hRsub hq have hne : p ≠ q := (Finset.ne_of_mem_erase hq).symm have hpq := hdisj hp' hqP hne have hsub : t ∩ q ⊆ p ∩ q := by intro v hv obtain ⟨hvt,hvq⟩ := Finset.mem_inter.mp hv have hvp : v ∈ p := by simp only [t, Finset.mem_insert, Finset.mem_singleton] at hvt simp only [p, Finset.mem_insert, Finset.mem_singleton] rcases hvt with rfl | rfl | rfl · exact Or.inl rfl · exact Or.inr (Or.inl rfl) · exact False.elim (hxP q hqP hvq) exact Finset.mem_inter.mpr ⟨hvp,hvq⟩ have hc := Finset.card_le_card hsub omega
The candidate packing Q is pairwise edge-disjoint.
The subfamily R = P \ {p} is pairwise edge-disjoint as a subset of P. Adjoining t preserves this property because t shares at most one vertex with every member of R, and finset intersection cardinality is symmetric.
uses
Finset.coe_insert,Finset.inter_commhave hRpair : (R : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by intro s hs u hu hne exact hdisj (hRsub hs) (hRsub hu) hne have hQpair : (Q : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by change ((insert t R : Finset (Finset (Fin n))) : Set (Finset (Fin n))).Pairwise _ rw [Finset.coe_insert] refine hRpair.insert ?_ intro q hq _ have hh := htpair q hq exact ⟨hh, by rw [Finset.inter_comm]; exact hh⟩
The packing Q contains exactly as many triangles as P: |Q| = |P|.
Since t ∉ P, t ∉ R, so inserting t into R gives |Q| = |R| + 1. Since p ∈ P, erasing p gives |R| = |P| - 1. Since P is nonempty (it contains p), |Q| = (|P| - 1) + 1 = |P|.
uses
Finset.card_insert_of_notMem,Finset.card_erase_of_mem,Finset.card_pos.mprhave hQcard : Q.card = P.card := by have htR : t ∉ R := fun h => htP (hRsub h) rw [show Q = insert t R by rfl, Finset.card_insert_of_notMem htR] rw [show R = P.erase p by rfl, Finset.card_erase_of_mem hp'] have hpos : 0 < P.card := Finset.card_pos.mpr ⟨p,hp'⟩ omega
If some q ∈ P \ {p} contains c, then the vertex support of P is a subset of the vertex support of Q: V(P) ⊆ V(Q).
Suppose some q ∈ P with q ≠ p contains c; then q ∈ R ⊆ Q. For any vertex v in the vertex support of P, v belongs to some triangle r ∈ P. If r ≠ p, then r ∈ R ⊆ Q, so v ∈ V(Q). If r = p = {a, b, c}, then: if v = a or v = b, v ∈ t ∈ Q; if v = c, v ∈ q ∈ Q since c ∈ q. In every case, v is covered by Q.
uses
Finset.mem_erase.mpr,Finset.mem_insert_of_mem,Finset.mem_biUnion.mp,Finset.mem_insert,Finset.mem_singleton,Finset.mem_biUnion.mprintro q hq hqp hcq have hqR : q ∈ R := Finset.mem_erase.mpr ⟨hqp,hq⟩ have hqQ : q ∈ Q := Finset.mem_insert_of_mem hqR have hsub : P.biUnion id ⊆ Q.biUnion id := by intro v hv obtain ⟨r,hr,hvr⟩ := Finset.mem_biUnion.mp hv by_cases hrp : r = p · subst r change v ∈ ({a,b,c} : Finset (Fin n)) at hvr simp only [Finset.mem_insert, Finset.mem_singleton] at hvr rcases hvr with rfl | rfl | rfl · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩ · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩ · exact Finset.mem_biUnion.mpr ⟨q,hqQ,hcq⟩ · have hrR : r ∈ R := Finset.mem_erase.mpr ⟨hrp,hr⟩ have hrQ : r ∈ Q := Finset.mem_insert_of_mem hrR exact Finset.mem_biUnion.mpr ⟨r,hrQ,hvr⟩ have hxQ : x ∈ Q.biUnion id := Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩
The vertex support of Q is strictly larger than that of P, contradicting the maximality of P.
We have V(P) ⊆ V(Q), and x ∈ t ∈ Q gives x ∈ V(Q), while x ∉ V(P). Hence V(P) ⊊ V(Q), so |V(P)| < |V(Q)|. However, Q is a valid edge-disjoint triangle packing of the same size as P, so by the support maximality of P, |V(Q)| ≤ |V(P)|. This contradiction shows that no triangle q ∈ P \ {p} can contain c.
uses
Finset.ssubset_iff_subset_ne.mpr,Finset.card_lt_cardhave hstrict : P.biUnion id ⊂ Q.biUnion id := by refine Finset.ssubset_iff_subset_ne.mpr ⟨hsub, ?_⟩ intro heq apply hx rw [heq] exact hxQ have hlt := Finset.card_lt_card hstrict have hle := hsupport Q hQtri hQpair hQcard omega
Finset.mem_biUnion.mpr- An element belongs to the union of a family of finsets if and only if it belongs to at least one finset in the family (reverse implication).
Finset.mem_biUnion.mp- An element belongs to the union of a family of finsets implies it belongs to at least one finset in the family.
Finset.mem_insert- An element belongs to `insert b s` if and only if it equals `b` or belongs to `s`.
Finset.mem_insert.mp- If an element belongs to `insert b s`, then it either equals `b` or belongs to `s`.
Finset.mem_singleton- An element belongs to the singleton `{a}` if and only if it equals `a`.
Finset.card_le_card- If one finset is a subset of another, its cardinality is less than or equal to that of the other.
Finset.card_le_two- A finset with at most two listed elements has cardinality at most 2.
Finset.mem_of_mem_erase- If an element belongs to `s.erase a`, then it belongs to `s`.
Finset.ne_of_mem_erase- If an element belongs to `s.erase a`, then it is not equal to `a`.
Finset.mem_inter.mp- If an element belongs to the intersection of two finsets, it belongs to both.
Finset.mem_inter.mpr- If an element belongs to both finsets, it belongs to their intersection.
Or.inl- From a proof of A, infer A ∨ B.
Or.inr- From a proof of B, infer A ∨ B.
False.elim- From a contradiction (False), any conclusion follows.
Finset.coe_insert- Coercing an inserted finset to a set equals the set-theoretic insertion into the coerced set.
Finset.inter_comm- Intersection of finsets is commutative: s ∩ t = t ∩ s.
Finset.card_insert_of_notMem- Inserting an element not in a finset increases its cardinality by 1.
Finset.card_erase_of_mem- Erasing an element present in a finset decreases its cardinality by 1.
Finset.card_pos.mpr- A nonempty finset has strictly positive cardinality.
Finset.mem_erase.mpr- If b ≠ a and b ∈ s, then b ∈ s.erase a.
Finset.mem_insert_of_mem- If an element belongs to s, it belongs to insert b s.
Finset.ssubset_iff_subset_ne.mpr- If s ⊆ t and s ≠ t, then s is a strict subset of t (s ⊂ t).
Finset.card_lt_card- A strict subset of a finset has strictly smaller cardinality.
- The distinctness of a and b (step 2, lines 15–24) is proved in the source but never actually referenced in the rest of the proof.
- Arithmetic constraints and cardinality comparisons (lines 24, 56, 72, 99) are closed by the `omega` decision procedure.
- Case analysis on finite set memberships (e.g. lines 19–20) is handled using `aesop` and `simp`.
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_support_max_packing_outside_swap_private (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hsupport : ∀ 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) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hface : G.IsNClique 3 ({a,b,x} : Finset (Fin n))) : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → c ∉ q := by classical let p : Finset (Fin n) := {a,b,c} let t : Finset (Fin n) := {a,b,x} have hp' : p ∈ P := hp have hxP : ∀ q ∈ P, x ∉ q := by intro q hq hqx apply hx exact Finset.mem_biUnion.mpr ⟨q,hq,hqx⟩ have hxp : x ∉ p := hxP p hp' have hab : a ≠ b := by intro h have hs : p ⊆ ({a,c} : Finset (Fin n)) := by intro v hv simp only [p, Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have htwo := Finset.card_le_two (a := a) (b := c) have hp3 := (htri p hp').card_eq omega have htP : t ∉ P := by intro ht have : x ∈ t := by simp [t] exact hxP t ht this let R : Finset (Finset (Fin n)) := P.erase p let Q : Finset (Finset (Fin n)) := insert t R have hQt : t ∈ Q := by simp [Q] have hRsub : R ⊆ P := by intro q hq; exact Finset.mem_of_mem_erase hq have hface' : G.IsNClique 3 t := hface have hQtri : ∀ s ∈ Q, G.IsNClique 3 s := by intro s hs rcases Finset.mem_insert.mp hs with rfl | hs · exact hface' · exact htri s (hRsub hs) have htpair : ∀ q ∈ R, (t ∩ q).card ≤ 1 := by intro q hq have hqP : q ∈ P := hRsub hq have hne : p ≠ q := (Finset.ne_of_mem_erase hq).symm have hpq := hdisj hp' hqP hne have hsub : t ∩ q ⊆ p ∩ q := by intro v hv obtain ⟨hvt,hvq⟩ := Finset.mem_inter.mp hv have hvp : v ∈ p := by simp only [t, Finset.mem_insert, Finset.mem_singleton] at hvt simp only [p, Finset.mem_insert, Finset.mem_singleton] rcases hvt with rfl | rfl | rfl · exact Or.inl rfl · exact Or.inr (Or.inl rfl) · exact False.elim (hxP q hqP hvq) exact Finset.mem_inter.mpr ⟨hvp,hvq⟩ have hc := Finset.card_le_card hsub omega have hRpair : (R : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by intro s hs u hu hne exact hdisj (hRsub hs) (hRsub hu) hne have hQpair : (Q : Set (Finset (Fin n))).Pairwise (fun s u => (s ∩ u).card ≤ 1) := by change ((insert t R : Finset (Finset (Fin n))) : Set (Finset (Fin n))).Pairwise _ rw [Finset.coe_insert] refine hRpair.insert ?_ intro q hq _ have hh := htpair q hq exact ⟨hh, by rw [Finset.inter_comm]; exact hh⟩ have hQcard : Q.card = P.card := by have htR : t ∉ R := fun h => htP (hRsub h) rw [show Q = insert t R by rfl, Finset.card_insert_of_notMem htR] rw [show R = P.erase p by rfl, Finset.card_erase_of_mem hp'] have hpos : 0 < P.card := Finset.card_pos.mpr ⟨p,hp'⟩ omega intro q hq hqp hcq have hqR : q ∈ R := Finset.mem_erase.mpr ⟨hqp,hq⟩ have hqQ : q ∈ Q := Finset.mem_insert_of_mem hqR have hsub : P.biUnion id ⊆ Q.biUnion id := by intro v hv obtain ⟨r,hr,hvr⟩ := Finset.mem_biUnion.mp hv by_cases hrp : r = p · subst r change v ∈ ({a,b,c} : Finset (Fin n)) at hvr simp only [Finset.mem_insert, Finset.mem_singleton] at hvr rcases hvr with rfl | rfl | rfl · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩ · exact Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩ · exact Finset.mem_biUnion.mpr ⟨q,hqQ,hcq⟩ · have hrR : r ∈ R := Finset.mem_erase.mpr ⟨hrp,hr⟩ have hrQ : r ∈ Q := Finset.mem_insert_of_mem hrR exact Finset.mem_biUnion.mpr ⟨r,hrQ,hvr⟩ have hxQ : x ∈ Q.biUnion id := Finset.mem_biUnion.mpr ⟨t,hQt,by simp [t]⟩ have hstrict : P.biUnion id ⊂ Q.biUnion id := by refine Finset.ssubset_iff_subset_ne.mpr ⟨hsub, ?_⟩ intro heq apply hx rw [heq] exact hxQ have hlt := Finset.card_lt_card hstrict have hle := hsupport Q hQtri hQpair hQcard omega