simple_graph_support_max_packing_external_k4_decreases_packing
If a maximum triangle packing has maximum vertex support, a packed face abc and an outside fourth vertex x spanning a four-clique force deletion of ab and cx to decrease the packing number.
Statement
theorem simple_graph_support_max_packing_external_k4_decreases_packing (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) (hmax : P.card = simple_graph_triangle_packing_number G) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b),s(c,x)}) < simple_graph_triangle_packing_number G
- Source
- Support-maximal reduction of the fully forced K4 branch of the triangle-packing campaign; no novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_support_max_packing_outside_swap_privateIf P has maximum vertex support among triangle packings of its size, replacing packed triangle abc by abx with x outside P is possible…
- 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_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_pair_stable_support_max_k4_anchor_internalIn a two-edge-stable graph, every fourth vertex completing a packed triangle of a support-maximal maximum triangle packing to a…
The proof, explained
To show that deleting edges $ab$ and $cx$ strictly decreases the triangle packing number, the proof establishes that $a$ and $b$ are private to the packed triangle $\{a,b,c\}$ in $P$ (appearing in no other triangle of the packing). Because $\{a,b,c,x\}$ forms a 4-clique with an external vertex $x$, the faces $\{b,c,x\}$ and $\{a,c,x\}$ are also triangles. If either $a$ or $b$ were shared with another triangle in $P$, swapping $\{a,b,c\}$ for one of these faces would produce an equal-sized packing covering more vertices, contradicting the maximality of $P$'s vertex support. Having shown that both $a$ and $b$ are private, the theorem follows by invoking the reduction lemma `simple_graph_external_k4_private_pair_decreases_packing`.
The vertices $a$, $b$, $c$, and $x$ are pairwise distinct.
For each of the six pairs among $a, b, c, x$, assuming the two vertices are equal implies that $\{a,b,c,x\}$ is contained in a set of at most three elements. By `Finset.card_le_card` and `Finset.card_le_three`, its cardinality would be at most 3. But $\{a,b,c,x\}$ spans a 4-clique, so its cardinality is 4. Linear arithmetic (`omega`) yields a contradiction ($4 \le 3$) in each case, establishing $a \neq b$, $a \neq c$, $a \neq x$, $b \neq c$, $b \neq x$, and $c \neq x$.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_le_threeclassical have hab : a ≠ b := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := c) (c := x) have h4 := hk4.card_eq omega have hac : a ≠ c := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := x) have h4 := hk4.card_eq omega have hax : a ≠ x := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hbc : b ≠ c := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := x) have h4 := hk4.card_eq omega have hbx : b ≠ x := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hcx : c ≠ x := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega
The subsets $\{b,c,x\}$ and $\{a,c,x\}$ are triangles (3-cliques) in $G$.
Since $\{a,b,c,x\}$ is a 4-clique in $G$, any subset of its vertices spans a clique by `SimpleGraph.IsClique.subset`. Since the vertices are pairwise distinct, both $\{b,c,x\}$ and $\{a,c,x\}$ have cardinality 3, so they are 3-cliques in $G$.
uses
SimpleGraph.IsClique.subset,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,Ne.symmhave hface1 : G.IsNClique 3 ({b,c,x} : Finset (Fin n)) := by refine ⟨SimpleGraph.IsClique.subset ?_ hk4.isClique, ?_⟩ · intro v hv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop · simp [hbc,hbx,hcx,Ne.symm hbc,Ne.symm hbx,Ne.symm hcx] have hface2 : G.IsNClique 3 ({a,c,x} : Finset (Fin n)) := by refine ⟨SimpleGraph.IsClique.subset ?_ hk4.isClique, ?_⟩ · intro v hv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop · simp [hac,hax,hcx,Ne.symm hac,Ne.symm hax,Ne.symm hcx]
The vertices $a$ and $b$ are private to $\{a,b,c\}$ in the packing $P$: no other triangle in $P$ contains $a$ or $b$.
Applying `simple_graph_support_max_packing_outside_swap_private` to triangle $\{b,c,a\} \in P$ and triangle $\{b,c,x\}$ shows that $a$ cannot belong to any other triangle in $P$, because swapping $\{b,c,a\}$ for $\{b,c,x\}$ would otherwise increase the vertex support. Symmetrically, applying it to $\{a,c,b\} \in P$ and $\{a,c,x\}$ shows that $b$ cannot belong to any other triangle in $P$. Hence, every triangle $q \in P$ distinct from $\{a,b,c\}$ contains neither $a$ nor $b$.
uses
Finset.mem_insert,Finset.mem_singleton,simple_graph_support_max_packing_outside_swap_privatehave heq1 : ({b,c,a} : Finset (Fin n)) = {a,b,c} := by ext v; simp only [Finset.mem_insert, Finset.mem_singleton]; tauto have heq2 : ({a,c,b} : Finset (Fin n)) = {a,b,c} := by ext v; simp only [Finset.mem_insert, Finset.mem_singleton]; tauto have hp1 : ({b,c,a} : Finset (Fin n)) ∈ P := by rwa [heq1] have hp2 : ({a,c,b} : Finset (Fin n)) ∈ P := by rwa [heq2] have ha := simple_graph_support_max_packing_outside_swap_private n G P htri hdisj hsupport b c a x hp1 hx hface1 have hb := simple_graph_support_max_packing_outside_swap_private n G P htri hdisj hsupport a c b x hp2 hx hface2 have hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → a ∉ q ∧ b ∉ q := by intro q hq hne constructor · apply ha q hq rwa [heq1] · apply hb q hq rwa [heq2]
Deleting edges $ab$ and $cx$ strictly decreases the triangle packing number of $G$.
With $a$ and $b$ verified to be private to the packed triangle $\{a,b,c\}$ and $x$ outside the support spanning a 4-clique on $\{a,b,c,x\}$, `simple_graph_external_k4_private_pair_decreases_packing` directly implies that the triangle packing number of $G \setminus \{ab, cx\}$ is strictly less than that of $G$.
uses
simple_graph_external_k4_private_pair_decreases_packingexact simple_graph_external_k4_private_pair_decreases_packing n G P a b c x htri hdisj hmax hp hx hprivate hk4
Finset.card_le_card- If $s \subseteq t$ for finite sets $s$ and $t$, then $|s| \le |t|$.
Finset.card_le_three- For any elements $a, b, c$, the set $\{a, b, c\}$ has cardinality at most 3.
Finset.mem_insert- An element belongs to $\text{insert}(b, s)$ if and only if it equals $b$ or belongs to $s$.
Finset.mem_singleton- An element belongs to the singleton set $\{a\}$ if and only if it equals $a$.
Finset.mem_coe- An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Ne.symm- Inequality is symmetric: if $a \neq b$, then $b \neq a$.
SimpleGraph.IsClique.subset- Any subset of a clique in a graph is also a clique.
simple_graph_support_max_packing_outside_swap_private- In a maximum triangle packing $P$ with maximum vertex support, if $\{a,b,c\} \in P$ and an external vertex $x$ forms a triangle $\{a,b,x\}$, then $c$ belongs to no other triangle in $P$ (it is private to $\{a,b,c\}$).
simple_graph_external_k4_private_pair_decreases_packing- If $\{a,b,c\}$ belongs to a maximum triangle packing $P$, an outside vertex $x$ spans a 4-clique with $\{a,b,c\}$, and vertices $a$ and $b$ appear in no other triangle of $P$, then deleting edges $ab$ and $cx$ strictly decreases the triangle packing number.
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_external_k4_decreases_packing (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) (hmax : P.card = simple_graph_triangle_packing_number G) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b),s(c,x)}) < simple_graph_triangle_packing_number G := by classical have hab : a ≠ b := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := c) (c := x) have h4 := hk4.card_eq omega have hac : a ≠ c := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := x) have h4 := hk4.card_eq omega have hax : a ≠ x := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hbc : b ≠ c := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,x} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := x) have h4 := hk4.card_eq omega have hbx : b ≠ x := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hcx : c ≠ x := by intro h have hs : ({a,b,c,x} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ clear * - h hv aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hface1 : G.IsNClique 3 ({b,c,x} : Finset (Fin n)) := by refine ⟨SimpleGraph.IsClique.subset ?_ hk4.isClique, ?_⟩ · intro v hv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop · simp [hbc,hbx,hcx,Ne.symm hbc,Ne.symm hbx,Ne.symm hcx] have hface2 : G.IsNClique 3 ({a,c,x} : Finset (Fin n)) := by refine ⟨SimpleGraph.IsClique.subset ?_ hk4.isClique, ?_⟩ · intro v hv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop · simp [hac,hax,hcx,Ne.symm hac,Ne.symm hax,Ne.symm hcx] have heq1 : ({b,c,a} : Finset (Fin n)) = {a,b,c} := by ext v; simp only [Finset.mem_insert, Finset.mem_singleton]; tauto have heq2 : ({a,c,b} : Finset (Fin n)) = {a,b,c} := by ext v; simp only [Finset.mem_insert, Finset.mem_singleton]; tauto have hp1 : ({b,c,a} : Finset (Fin n)) ∈ P := by rwa [heq1] have hp2 : ({a,c,b} : Finset (Fin n)) ∈ P := by rwa [heq2] have ha := simple_graph_support_max_packing_outside_swap_private n G P htri hdisj hsupport b c a x hp1 hx hface1 have hb := simple_graph_support_max_packing_outside_swap_private n G P htri hdisj hsupport a c b x hp2 hx hface2 have hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → a ∉ q ∧ b ∉ q := by intro q hq hne constructor · apply ha q hq rwa [heq1] · apply hb q hq rwa [heq2] exact simple_graph_external_k4_private_pair_decreases_packing n G P a b c x htri hdisj hmax hp hx hprivate hk4