AFTD Auto-Formalizing Theoretical Domains

simple_graph_support_max_packing_external_k4_decreases_packing

theoremverified

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
Used by 1

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`.

  1. 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$.

    lines 6–72

    uses Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_le_three

      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
  2. 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$.

    lines 73–84

    uses SimpleGraph.IsClique.subset, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, Ne.symm

      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]
  3. 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$.

    lines 85–97

    uses Finset.mem_insert, Finset.mem_singleton, simple_graph_support_max_packing_outside_swap_private

      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]
  4. 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$.

    line 98

    uses simple_graph_external_k4_private_pair_decreases_packing

      exact 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

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
See it in the graphDiscuss this resultChallenge it