simple_graph_opposite_pair_stable_k4_attachment
Let 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 edge of any packed triangle. If deleting the opposite edges ab and cx preserves the packing number, then another triangle t of P contains a vertex y outside the four-clique and either t contains a or b and xy is an edge, or t contains x and ay or by is an edge.
Statement
theorem simple_graph_opposite_pair_stable_k4_attachment (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) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y)))
- 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 3
- 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_k4_attachment_of_two_triangle_edge_coversLet two families P and Q meet every triangle of a graph in an edge, with all members of Q triangles. In a four-clique abcx, suppose no…
- Used by 1
- 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…
The proof, explained
To find the required triangle attachment in P, we exploit the stability assumption: deleting the opposite edges ab and cx yields a subgraph H with the same triangle packing number. A maximum triangle packing Q in H is also a maximum packing in G, so both P and Q edge-cover all triangles of G. Since the edges ab and cx were deleted, no triangle in Q contains both endpoints of either edge; combined with the hypothesis that P avoids ax and bx, the two-cover attachment lemma simple_graph_k4_attachment_of_two_triangle_edge_covers supplies the desired triangle in P.
Define H as G without the edges ab and cx, and observe H ≤ G.
We construct H by deleting the two opposite edges from G and note that H is a subgraph of G by SimpleGraph.deleteEdges_le.
uses
SimpleGraph.deleteEdges_leclassical let H := G.deleteEdges {s(a,b), s(c,x)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(a,b), s(c,x)}
There exists a maximum edge-disjoint triangle packing Q in H.
The set of sizes of edge-disjoint triangle packings in H is nonempty (the empty packing has size 0) and bounded above by the total number of vertex subsets. By Nat.sSup_mem, the supremum is achieved by some packing Q of triangles in H.
uses
Finset.card_le_univ,Nat.sSup_memlet A : Set ℕ := {k | ∃ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, H.IsNClique 3 t) ∧ (Q : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ Q.card = k} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset (Fin n)), ?_⟩ rintro k ⟨Q, _, _, rfl⟩ exact Finset.card_le_univ Q obtain ⟨Q, hQH, hQpair, hQcard⟩ := Nat.sSup_mem hne hbdd
Q is a triangle packing in G of size equal to the triangle packing number of G.
Since deleting {ab, cx} preserves the packing number, |Q| = ν₃(H) = ν₃(G). Moreover, because H ≤ G, every triangle in H is also a triangle in G.
have hQcard' : Q.card = simple_graph_triangle_packing_number G := by change Q.card = simple_graph_triangle_packing_number H at hQcard change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hstable omega have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by intro t ht; exact (hQH t ht).mono hHG
Every triangle in G shares an edge with some triangle in P, and also with some triangle in Q.
Because P and Q are both maximum edge-disjoint triangle packings in G, simple_graph_maximum_triangle_packing_edge_meets implies each of them is an edge cover of the triangles of G.
uses
simple_graph_maximum_triangle_packing_edge_meetshave hPc := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard'
The vertices a, b are distinct, and c, x are distinct.
If a = b, then {a, b, c, x} has at most 3 vertices, contradicting that it induces a 4-clique. Similarly, if c = x, the set has at most 3 vertices, again contradicting that it is a 4-clique.
uses
Finset.card_le_card,Finset.card_le_three,Finset.mem_insert,Finset.mem_singletonhave hab : a ≠ b := by intro h; subst b have hsub : ({a,a,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by simp have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := c) (c := x) have h4 := hk4.card_eq omega have hcx : c ≠ x := by intro h; subst x have hsub : ({a,b,c,c} : Finset (Fin n)) ⊆ {a,b,c} := by intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega
No triangle in Q contains both a and b, or both c and x.
Any triangle in Q is a clique in H. If it contained both a and b, ab would be an edge in H, contradicting the deletion of ab. Likewise, it cannot contain both c and x.
uses
SimpleGraph.deleteEdges_adj.mphave havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t) := by intro t ht constructor · intro h have hadj : H.Adj a b := (hQH t ht).isClique h.1 h.2 hab have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp) · intro h have hadj : H.Adj c x := (hQH t ht).isClique h.1 h.2 hcx have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp)
There exists a triangle t in P outside {a, b, c} with the specified attachment to x.
We apply simple_graph_k4_attachment_of_two_triangle_edge_covers to G, P, Q, and the 4-clique {a, b, c, x}, using the two edge-cover properties and the avoidance conditions for P and Q.
uses
simple_graph_k4_attachment_of_two_triangle_edge_coversexact simple_graph_k4_attachment_of_two_triangle_edge_covers n G P Q a b c x hk4 hPc hQc hQG hspokes havoidThe main theorem simple_graph_opposite_pair_stable_k4_attachment holds.
The main theorem follows immediately from stable_k4_attachment_in604, ignoring the extra hypothesis that {a, b, c} ∈ P.
uses
stable_k4_attachment_in604theorem simple_graph_opposite_pair_stable_k4_attachment (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) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by exact stable_k4_attachment_in604 n G P a b c x htri hdisj hmax hk4 hspokes hstable
SimpleGraph.deleteEdges_le- A subgraph obtained by deleting edges is a subgraph of the original graph.
Finset.card_le_univ- Any finite subset of a finite type has cardinality at most the cardinality of the whole type.
Nat.sSup_mem- A nonempty set of natural numbers bounded above contains its supremum.
simple_graph_maximum_triangle_packing_edge_meets- Every triangle in a graph shares at least an edge (two vertices) with some triangle in a maximum triangle packing.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to the other's.
Finset.card_le_three- A set of at most three elements has cardinality at most 3.
Finset.mem_insert- Finset membership in an inserted set is membership in the tail or equality to the head.
Finset.mem_singleton- Finset membership in a singleton is equality to the unique element.
SimpleGraph.deleteEdges_adj.mp- An edge in G.deleteEdges s is an edge of G that is not in s.
simple_graph_k4_attachment_of_two_triangle_edge_covers- Given a 4-clique with two triangle edge-covers satisfying the spoke-avoidance conditions, some triangle outside the clique connects to the fourth vertex.
stable_k4_attachment_in604- The core lemma establishing the attachment property for a maximum triangle packing with stable deletion of opposite edges in a 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 Sym2set_option maxRecDepth 10000set_option maxHeartbeats 3000000theorem stable_k4_attachment_in604 (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) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by classical let H := G.deleteEdges {s(a,b), s(c,x)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(a,b), s(c,x)} let A : Set ℕ := {k | ∃ Q : Finset (Finset (Fin n)), (∀ t ∈ Q, H.IsNClique 3 t) ∧ (Q : Set (Finset (Fin n))).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ Q.card = k} have hne : A.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩ have hbdd : BddAbove A := by refine ⟨Fintype.card (Finset (Fin n)), ?_⟩ rintro k ⟨Q, _, _, rfl⟩ exact Finset.card_le_univ Q obtain ⟨Q, hQH, hQpair, hQcard⟩ := Nat.sSup_mem hne hbdd have hQcard' : Q.card = simple_graph_triangle_packing_number G := by change Q.card = simple_graph_triangle_packing_number H at hQcard change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hstable omega have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by intro t ht; exact (hQH t ht).mono hHG have hPc := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard' have hab : a ≠ b := by intro h; subst b have hsub : ({a,a,c,x} : Finset (Fin n)) ⊆ {a,c,x} := by simp have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := c) (c := x) have h4 := hk4.card_eq omega have hcx : c ≠ x := by intro h; subst x have hsub : ({a,b,c,c} : Finset (Fin n)) ⊆ {a,b,c} := by intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t) := by intro t ht constructor · intro h have hadj : H.Adj a b := (hQH t ht).isClique h.1 h.2 hab have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp) · intro h have hadj : H.Adj c x := (hQH t ht).isClique h.1 h.2 hcx have hnot := (SimpleGraph.deleteEdges_adj.mp hadj).2 exact hnot (by simp) exact simple_graph_k4_attachment_of_two_triangle_edge_covers n G P Q a b c x hk4 hPc hQc hQG hspokes havoidtheorem simple_graph_opposite_pair_stable_k4_attachment (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) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (hstable : simple_graph_triangle_packing_number (G.deleteEdges {s(a,b), s(c,x)}) = simple_graph_triangle_packing_number G) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by exact stable_k4_attachment_in604 n G P a b c x htri hdisj hmax hk4 hspokes hstable