simple_graph_external_k4_private_pair_decreases_packing
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
- 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).
- simple_graph_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- simple_graph_opposite_pair_stable_k4_attachmentLet P be a maximum edge-disjoint triangle packing containing abc, and let x complete abc to a four-clique. Suppose neither ax nor bx is an…
- simple_graph_triangle_packing_number_monoTriangle packing number is monotone under subgraph inclusion: if H ≤ G, then ν(H) ≤ ν(G).
- 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
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.
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.
uses
simple_graph_triangle_packing_number_mono,SimpleGraph.deleteEdges_leclassical 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
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).
uses
Finset.mem_biUnion.mprhave 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
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.
uses
simple_graph_opposite_pair_stable_k4_attachmentobtain ⟨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 hstableBoth 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.
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
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 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