AFTD Auto-Formalizing Theoretical Domains

simple_graph_external_k4_private_pair_decreases_packing

theoremverified

Let 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 vertices of P and abcx is a four-clique, then deleting the opposite edges ab and cx decreases the triangle packing number. No forcing hypothesis is needed.

Statement

theorem simple_graph_external_k4_private_pair_decreases_packing (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hprivate : ∀ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) → a ∉ t ∧ b ∉ t) (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
Structural reduction of the pair-stable forced-K4 branch of simple_graph_triangle_cover_number_le_two_mul_packing_number.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

We argue by contradiction: if deleting the opposite edges ab and cx did not strictly decrease the triangle packing number, the packing number would remain unchanged since edge deletion is monotone. Because x lies outside all triangles in P, no triangle can contain x together with a or b. An attachment lemma for opposite edges of a 4-clique then forces the existence of another triangle in P containing a, b, or x. But a and b are private to abc and x is external to P, yielding an immediate contradiction.

  1. Assuming the triangle packing number does not strictly decrease, it must remain unchanged after deleting the edges ab and cx.

    We proceed by contradiction (line 5), assuming that deleting the opposite edges {a, b} and {c, x} does not strictly decrease the triangle packing number. By monotonicity of the packing number under subgraph inclusion (simple_graph_triangle_packing_number_mono and SimpleGraph.deleteEdges_le), the packing number after edge deletion is at most the original packing number. Combining these two inequalities via linear arithmetic (omega, line 10) shows that the packing number must be exactly preserved.

    lines 4–10

    uses simple_graph_triangle_packing_number_mono, SimpleGraph.deleteEdges_le

      classical
      by_contra hn
      have hle : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) ≤
          simple_graph_triangle_packing_number G :=
        simple_graph_triangle_packing_number_mono G _ (SimpleGraph.deleteEdges_le _)
      have hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) =
          simple_graph_triangle_packing_number G := by omega
  2. The vertex x belongs to no triangle in P, so no triangle in P contains x together with a or together with b.

    By hypothesis, x does not belong to the union of all triangles in P. Thus, for any triangle t in P, x cannot belong to t (lines 11–14, using Finset.mem_biUnion.mpr). In particular, no triangle t in P can contain both x and a, or both x and b (lines 15–16).

    lines 11–16

    uses Finset.mem_biUnion.mpr

      have hxnot : ∀ t ∈ P, x ∉ t := by
        intro t ht hxt
        apply hx
        exact Finset.mem_biUnion.mpr ⟨t, ht, hxt⟩
      have hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t) := by
        intro t ht; constructor <;> intro h <;> exact hxnot t ht h.1
  3. There exists another triangle t in P that either contains a or b and is adjacent to x, or contains x and is adjacent to a or b.

    We invoke simple_graph_opposite_pair_stable_k4_attachment using the stability of the packing number and the fact that no triangle in P contains x with a or b. This yields a triangle t in P distinct from {a, b, c} and a vertex y in t outside {a, b, c, x} satisfying the attachment condition.

    lines 17–18

    uses simple_graph_opposite_pair_stable_k4_attachment

      obtain ⟨t, ht, htne, y, hyt, hyout, hatt⟩ :=
        simple_graph_opposite_pair_stable_k4_attachment n G P a b c x htri hdisj hmax hp hk4 hspokes hstable
  4. Both branches of the attachment condition yield a contradiction, completing the proof.

    We case-split on the attachment condition (line 19). If t contains a or b, this contradicts the hypothesis hprivate that a and b are private to {a, b, c} among all triangles in P (lines 20–23). If t contains x, this contradicts our earlier deduction that x belongs to no triangle in P (line 24). Both cases are impossible, contradicting the assumption that the packing number was preserved.

    lines 19–24

      rcases hatt with ⟨hab, hxy⟩ | ⟨hxt, hadj⟩
      · have hpv := hprivate t ht htne
        rcases hab with ha | hb
        · exact hpv.1 ha
        · exact hpv.2 hb
      · exact hxnot t ht hxt
simple_graph_triangle_packing_number_mono
If H is a subgraph of G, then the triangle packing number of H is at most that of G.
SimpleGraph.deleteEdges_le
Deleting a set of edges from a graph yields a subgraph of the original graph.
Finset.mem_biUnion.mpr
An element belongs to the union of a family of sets if and only if it belongs to at least one set in the family.
simple_graph_opposite_pair_stable_k4_attachment
In a graph with a maximum triangle packing P containing {a,b,c} and a 4-clique on {a,b,c,x}, if deleting edges ab and cx preserves the packing number and no triangle in P contains both x and a or x and b, then there is another triangle t in P sharing a vertex with {a,b} or containing x, and attached to the rest of the 4-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

open scoped Sym2theorem simple_graph_external_k4_private_pair_decreases_packing (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hx : x ∉ P.biUnion id) (hprivate : ∀ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) → a ∉ t ∧ b ∉ t) (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  by_contra hn  have hle : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) ≤      simple_graph_triangle_packing_number G :=    simple_graph_triangle_packing_number_mono G _ (SimpleGraph.deleteEdges_le _)  have hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) =      simple_graph_triangle_packing_number G := by omega  have hxnot : ∀ t ∈ P, x ∉ t := by    intro t ht hxt    apply hx    exact Finset.mem_biUnion.mpr ⟨t, ht, hxt⟩  have hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t) := by    intro t ht; constructor <;> intro h <;> exact hxnot t ht h.1  obtain ⟨t, ht, htne, y, hyt, hyout, hatt⟩ :=    simple_graph_opposite_pair_stable_k4_attachment n G P a b c x htri hdisj hmax hp hk4 hspokes hstable  rcases hatt with ⟨hab, hxy⟩ | ⟨hxt, hadj⟩  · have hpv := hprivate t ht htne    rcases hab with ha | hb    · exact hpv.1 ha    · exact hpv.2 hb  · exact hxnot t ht hxt
See it in the graphDiscuss this resultChallenge it