simple_graph_pair_stable_support_max_k4_anchor_internal
In a two-edge-stable graph, every fourth vertex completing a packed triangle of a support-maximal maximum triangle packing to a four-clique already belongs to the packing vertex support.
Statement
theorem simple_graph_pair_stable_support_max_k4_anchor_internal (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) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) : x ∈ P.biUnion id
- Source
- Internal-anchor reduction for the general fully forced triangle-packing residual; no novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- 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_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…
The proof, explained
The proof argues by contradiction. If the fourth vertex x extending a packed triangle {a, b, c} to a 4-clique lay outside the vertex support of the support-maximal maximum packing P, deleting the two distinct edges s(a, b) and s(c, x) would strictly decrease the triangle packing number by simple_graph_support_max_packing_external_k4_decreases_packing. However, the graph is two-edge-stable, so deleting any two distinct edges preserves the packing number. This contradiction forces x to already belong to the vertex support of P.
The four vertices a, b, c, and x forming the 4-clique are pairwise distinct.
Because {a, b, c, x} is a 4-clique, its cardinality is 4. If any two vertices were equal, the set {a, b, c, x} would be contained in a 3-element set, which by Finset.card_le_card and Finset.card_le_three would imply that its cardinality is at most 3. This contradiction shows that a ≠ b, a ≠ c, a ≠ x, b ≠ c, b ≠ x, and c ≠ x.
uses
Finset.card_le_card,Finset.card_le_three,Finset.mem_insert,Finset.mem_singletonclassical 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
Assuming for contradiction that x lies outside the packing support, s(a, b) and s(c, x) are two distinct edges of G.
Suppose for contradiction that x ∉ ⋃ P. Because {a, b, c, x} is a 4-clique, any two distinct vertices in it are joined by an edge in G. Since a ≠ b and c ≠ x, both s(a, b) and s(c, x) are edges of G. Furthermore, because all four vertices are distinct, Sym2.eq_iff verifies that the two edges are distinct: s(a, b) ≠ s(c, x).
uses
Sym2.eq_iffby_contra hx have he : s(a,b) ∈ G.edgeSet := by have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp exact hk4.isClique ha hb hab have hf : s(c,x) ∈ G.edgeSet := by have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hx' : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp exact hk4.isClique hc hx' hcx have hef : s(a,b) ≠ s(c,x) := by simp [Sym2.eq_iff,hac,hax,hbc,hbx]
Deleting the two edges contradicts the two-edge stability of G, proving x must belong to the packing support.
By simple_graph_support_max_packing_external_k4_decreases_packing, deleting the two edges s(a, b) and s(c, x) strictly decreases the triangle packing number of G. On the other hand, the two-edge stability hypothesis (hstable) asserts that deleting any two distinct edges leaves the triangle packing number unchanged. Linear arithmetic (omega) derives False from this contradiction, concluding that x ∈ ⋃ P.
uses
simple_graph_support_max_packing_external_k4_decreases_packinghave hd := simple_graph_support_max_packing_external_k4_decreases_packing n G P htri hdisj hsupport hmax a b c x hp hx hk4 have hs := hstable s(a,b) s(c,x) he hf hef omega
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t.
Finset.card_le_three- Any set formed by inserting three elements into the empty set has cardinality at most 3.
Finset.mem_insert- An element belongs to 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.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if {x, y} = {z, w}.
simple_graph_support_max_packing_external_k4_decreases_packing- If P is a maximum triangle packing with maximal vertex support and a packed triangle {a, b, c} extends to a 4-clique with an external vertex x, deleting {a, b} and {c, x} strictly decreases the triangle packing number.
- Lines 7–72 carry out formal verification that the vertices a, b, c, x forming the 4-clique are pairwise distinct; on paper, this is taken as immediate from the definition of an n-clique.
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_pair_stable_support_max_k4_anchor_internal (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) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (a b c x : Fin n) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) : x ∈ P.biUnion id := 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 by_contra hx have he : s(a,b) ∈ G.edgeSet := by have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp exact hk4.isClique ha hb hab have hf : s(c,x) ∈ G.edgeSet := by have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hx' : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp exact hk4.isClique hc hx' hcx have hef : s(a,b) ≠ s(c,x) := by simp [Sym2.eq_iff,hac,hax,hbc,hbx] have hd := simple_graph_support_max_packing_external_k4_decreases_packing n G P htri hdisj hsupport hmax a b c x hp hx hk4 have hs := hstable s(a,b) s(c,x) he hf hef omega