simple_graph_pair_stable_vertex_link_not_four_cycle
In a two-edge-stable graph, the graph induced by the neighborhood of any vertex cannot be exactly a four-cycle after isolated vertices are discarded.
Statement
theorem simple_graph_pair_stable_vertex_link_not_four_cycle (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) (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 d : Fin n) (hdist : ({a,b,c,d} : Finset (Fin n)).card = 4) : (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)) ≠ ({s(a,b),s(b,c),s(c,d),s(d,a)} : Finset (Sym2 (Fin n)))
- Source
- Two-edge-stable triangle-packing residual; experiment 20286. No novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- Used by 1
- simple_graph_pair_stable_active_vertex_at_least_five_trianglesIn a finite graph whose maximum triangle-packing number survives every two-edge deletion, any vertex that lies in a triangle lies in at…
The proof, explained
We argue by contradiction. Suppose the link graph of vertex x is the four-cycle (a, b, c, d). Removing the two edges ab and bc preserves the triangle packing number by two-edge-stability, so any maximum triangle packing Q of the reduced graph is also a maximum triangle packing of the original graph. By maximality, the triangles {x, a, b} and {x, b, c} must each share an edge with some triangle in Q; since the deleted edges cannot be used and no packing triangle can contain both x and b, these triangles must contain {x, a} and {x, c} respectively. Analyzing the link forces both packing triangles to also contain the fourth vertex d, meaning two distinct triangles in the packing share the edge xd, a contradiction.
Helper lemma (in693_cycle_two_of_three): if a set contains at least two elements of {a, b, x}, it contains at least one of the pairs {a, b}, {a, x}, or {b, x}.
We argue by contradiction. If none of the three pairs were contained in s, then any two elements u, v in s ∩ {a, b, x} would have to be equal, so the intersection would have cardinality at most 1 by Finset.card_le_one.mpr, contradicting that its cardinality is at least 2.
uses
Finset.card_le_one.mpr,Finset.mem_inter,Finset.mem_insert,Finset.mem_singletonclassical by_contra hn have hle : (s ∩ {a,b,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro u hu v hv simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hu hv aesop omega
Helper lemma (in693_cycle_third): any 3-element set containing two elements a and x must contain a third distinct element.
We argue by contradiction. If no such element exists, then every element of s must be equal to a or x, meaning s ⊆ {a, x}. By Finset.card_le_card and Finset.card_le_two, |s| ≤ |{a, x}| ≤ 2, contradicting |s| = 3.
uses
not_exists,not_and,Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_le_twoclassical by_contra hn have hsub : s ⊆ {a,x} := by intro y hy simp only [not_exists, not_and] at hn simp only [Finset.mem_insert, Finset.mem_singleton] by_contra hn2 exact hn y hy (by aesop) (by aesop) have hc := Finset.card_le_card hsub have htwo := Finset.card_le_two (a := a) (b := x) omega
Assume for contradiction that the link of x is the 4-cycle on vertices a, b, c, d.
We introduce the hypothesis hlinkeq that the edges induced by the neighborhood of x form the 4-cycle {s(a,b), s(b,c), s(c,d), s(d,a)}.
classical intro hlinkeqThe vertices a, b, c, d are pairwise distinct.
If any two of a, b, c, d were equal, the set {a, b, c, d} would be a subset of a 3-element set and thus have cardinality at most 3 by Finset.card_le_three and Finset.card_le_card, contradicting the hypothesis that its cardinality is 4.
uses
Finset.card_le_card,Finset.card_le_threehave hab : a ≠ b := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,c,d} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := c) (c := d) omega have hac : a ≠ c := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,d} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := d) omega have had : a ≠ d := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) omega have hbc : b ≠ c := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,d} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := d) omega have hbd : b ≠ d := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) omega have hcd : c ≠ d := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) omega
The edges between neighbors of x are precisely the cycle edges, and x is distinct from each of a, b, c, d.
By definition of the filtered link graph, any edge between neighbors of x must be one of the four cycle edges, and conversely each cycle edge is an edge of G with both endpoints adjacent to x. Since x is adjacent to each vertex in the 4-cycle, it is distinct from all of them. Moreover, s(a,b) ≠ s(b,c) because a, b, c are pairwise distinct.
uses
Finset.mem_filter.mpr,SimpleGraph.mem_edgeFinset.mpr,Finset.mem_filter.mp,SimpleGraph.mem_edgeFinset.mp,Sym2.eq_iffhave hlink : ∀ u v, G.Adj x u → G.Adj x v → G.Adj u v → s(u,v) ∈ ({s(a,b),s(b,c),s(c,d),s(d,a)} : Finset (Sym2 (Fin n))) := by intro u v hxu hxv huv have hm : s(u,v) ∈ G.edgeFinset.filter (fun e => ∀ w ∈ e, G.Adj x w) := by apply Finset.mem_filter.mpr constructor · exact SimpleGraph.mem_edgeFinset.mpr huv · intro w hw have hw' : w = u ∨ w = v := by simpa using hw rcases hw' with rfl | rfl <;> assumption rwa [hlinkeq] at hm have hE : ∀ u v, s(u,v) ∈ ({s(a,b),s(b,c),s(c,d),s(d,a)} : Finset (Sym2 (Fin n))) → G.Adj u v ∧ G.Adj x u ∧ G.Adj x v := by intro u v h have hm : s(u,v) ∈ G.edgeFinset.filter (fun e => ∀ w ∈ e, G.Adj x w) := by rwa [hlinkeq] obtain ⟨he,hx⟩ := Finset.mem_filter.mp hm exact ⟨SimpleGraph.mem_edgeFinset.mp he, hx u (by simp), hx v (by simp)⟩ have habg := hE a b (by simp) have hbcg := hE b c (by simp) have hcdg := hE c d (by simp) have hdag := hE d a (by simp) have hxa : x ≠ a := habg.2.1.ne have hxb : x ≠ b := habg.2.2.ne have hxc : x ≠ c := hbcg.2.2.ne have hxd : x ≠ d := hcdg.2.2.ne have he : s(a,b) ∈ G.edgeSet := habg.1 have hf : s(b,c) ∈ G.edgeSet := hbcg.1 have hef : s(a,b) ≠ s(b,c) := by simp [Sym2.eq_iff, hab, hbc, hac]
There exists a maximum triangle packing Q of H = G \\ {s(a,b), s(b,c)} that is also a maximum triangle packing of G.
Let H be the graph obtained by deleting the two distinct edges s(a,b) and s(b,c) from G. By two-edge-stability, ν(H) = ν(G). We choose a maximum triangle packing Q of H, which attains this packing number by Nat.sSup_mem. Since H is a subgraph of G, every triangle in Q is a triangle in G, so Q is also a maximum triangle packing in G. Hence every triangle in G shares at least two vertices with some triangle in Q by simple_graph_maximum_triangle_packing_edge_meets.
uses
SimpleGraph.deleteEdges_le,Finset.card_le_univ,Nat.sSup_mem,simple_graph_maximum_triangle_packing_edge_meetslet H := G.deleteEdges {s(a,b), s(b,c)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(a,b), s(b,c)} 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 have hs := hstable s(a,b) s(b,c) he hf hef change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hs omega have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by intro t ht; exact (hQH t ht).mono hHG have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard'
No triangle in Q contains the deleted edges, and the third vertex of any triangle in Q containing x and v is adjacent to x in G and to v in H.
Because the edges s(a,b) and s(b,c) were deleted in H, no clique in H can contain both a and b, or both b and c. For any triangle q ∈ Q containing x and a vertex v ≠ x, the third vertex u provided by in693_cycle_third is adjacent to x in G and adjacent to v in H.
uses
SimpleGraph.deleteEdges_adj.mp,in693_cycle_third,Ne.symmhave havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (b ∈ t ∧ c ∈ t) := by intro t ht constructor · intro h have hadj : H.Adj a b := (hQH t ht).isClique h.1 h.2 hab exact (SimpleGraph.deleteEdges_adj.mp hadj).2 (by simp) · intro h have hadj : H.Adj b c := (hQH t ht).isClique h.1 h.2 hbc exact (SimpleGraph.deleteEdges_adj.mp hadj).2 (by simp) have hextract : ∀ q ∈ Q, ∀ v, x ∈ q → v ∈ q → v ≠ x → ∃ u ∈ q, u ≠ v ∧ u ≠ x ∧ G.Adj x u ∧ H.Adj v u := by intro q hq v hxq hvq hvx have hqcl := hQG q hq obtain ⟨u,huq,huv,hux⟩ := in693_cycle_third q v x hqcl.card_eq hvq hxq exact ⟨u,huq,huv,hux,hqcl.isClique hxq huq (Ne.symm hux), (hQH q hq).isClique hvq huq (Ne.symm huv)⟩ have hno_b : ∀ q ∈ Q, ¬ (x ∈ q ∧ b ∈ q) := by
No triangle in Q contains both x and b.
If a triangle q ∈ Q contained both x and b, its third vertex u would be adjacent to x in G and to b in H. Then the edge bu connects two neighbors of x, so bu must be an edge of the 4-cycle incident to b, meaning u = a or u = c. But this would mean bu is s(a,b) or s(b,c), which were both deleted in H, a contradiction.
uses
SimpleGraph.deleteEdges_adj.mp,Sym2.eq_iff,Ne.symmintro q hq h obtain ⟨u,huq,hub,hux,hxu,hbu⟩ := hextract q hq b h.1 h.2 (Ne.symm hxb) have hm := hlink b u habg.2.2 hxu (hHG hbu) simp only [Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] at hm have hu : u = a ∨ u = c := by aesop have hn := (SimpleGraph.deleteEdges_adj.mp hbu).2 rcases hu with rfl | rfl · apply hn; simp [Sym2.eq_iff] · apply hn; simp have hba : G.Adj b a := habg.1.symm
The triples {x, a, b} and {x, b, c} form triangles in G.
The vertices x, a, b are pairwise distinct and mutually adjacent in G, and similarly for x, b, c. Thus both form 3-cliques in G.
uses
Ne.symmhave hay : G.Adj a x := habg.2.1.symm have hby : G.Adj b x := habg.2.2.symm have hcb : G.Adj c b := hbcg.1.symm have hcy : G.Adj c x := hbcg.2.2.symm have htri1 : G.IsNClique 3 ({x,a,b} : Finset (Fin n)) := by constructor · intro u hu v hv huv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> aesop · simp [hxa,hxb,hab,Ne.symm hxa,Ne.symm hxb,Ne.symm hab] have htri2 : G.IsNClique 3 ({x,b,c} : Finset (Fin n)) := by constructor · intro u hu v hv huv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> aesop · simp [hxb,hxc,hbc,Ne.symm hxb,Ne.symm hxc,Ne.symm hbc] obtain ⟨q1,hq1,hm1⟩ := hQc {x,a,b} htri1
There exist triangles q₁ and q₂ in Q such that {x, a} ⊆ q₁ and {x, c} ⊆ q₂.
By maximality of Q, the triangle {x, a, b} shares at least two vertices with some q₁ ∈ Q. By in693_cycle_two_of_three, q₁ must contain {x, a}, {x, b}, or {a, b}. It cannot contain {x, b} by the previous step, nor {a, b} as that edge was deleted in H, so {x, a} ⊆ q₁. The same reasoning applied to {x, b, c} yields q₂ ∈ Q containing {x, c}.
uses
in693_cycle_two_of_three,False.elimobtain ⟨q2,hq2,hm2⟩ := hQc {x,b,c} htri2 have hx1a : x ∈ q1 ∧ a ∈ q1 := by rcases in693_cycle_two_of_three q1 x a b hm1 with h | h | h · exact h · exact False.elim (hno_b q1 hq1 h) · exact False.elim ((havoid q1 hq1).1 h) have hx2c : x ∈ q2 ∧ c ∈ q2 := by rcases in693_cycle_two_of_three q2 x b c hm2 with h | h | h · exact False.elim (hno_b q2 hq2 h) · exact h · exact False.elim ((havoid q2 hq2).2 h) have hd1 : d ∈ q1 := by
Both q₁ and q₂ contain the vertex d.
The third vertex u of q₁ is adjacent to x in G and to a in H. Since au is an edge between neighbors of x, it must be an edge of the 4-cycle incident to a, so u = b or u = d. Since q₁ cannot contain {a, b}, u must be d, so d ∈ q₁. Symmetrically, the third vertex of q₂ is adjacent to c, forcing it to be d as well.
uses
Ne.symm,Sym2.eq_iff,False.elimobtain ⟨u,huq,hua,hux,hxu,hau⟩ := hextract q1 hq1 a hx1a.1 hx1a.2 (Ne.symm hxa) have hm := hlink a u habg.2.1 hxu (hHG hau) simp only [Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] at hm have hu : u = b ∨ u = d := by aesop rcases hu with rfl | rfl · exact False.elim ((havoid q1 hq1).1 ⟨hx1a.2,huq⟩) · exact huq have hd2 : d ∈ q2 := by obtain ⟨u,huq,huc,hux,hxu,hcu⟩ := hextract q2 hq2 c hx2c.1 hx2c.2 (Ne.symm hxc) have hm := hlink c u hbcg.2.2 hxu (hHG hcu) simp only [Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] at hm have hu : u = b ∨ u = d := by aesop rcases hu with rfl | rfl · exact False.elim ((havoid q2 hq2).2 ⟨huq,hx2c.2⟩) · exact huq have hqne : q1 ≠ q2 := by
The triangles q₁ and q₂ are distinct.
If q₁ = q₂, then q₁ would contain the four distinct vertices x, a, c, and d. By Finset.card_le_card this implies 4 ≤ 3, an impossibility.
uses
Finset.card_le_card,Ne.symmintro h; subst q2 have hs : ({x,a,c,d} : Finset (Fin n)) ⊆ q1 := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl | rfl · exact hx1a.1 · exact hx1a.2 · exact hx2c.2 · exact hd1 have hcard := Finset.card_le_card hs have hfour : ({x,a,c,d} : Finset (Fin n)).card = 4 := by simp [hxa,hxc,hxd,hac,had,hcd,Ne.symm hxa,Ne.symm hxc,Ne.symm hxd,Ne.symm hac,Ne.symm had,Ne.symm hcd] have hc := (hQG q1 hq1).card_eq omega have hs : ({x,d} : Finset (Fin n)) ⊆ q1 ∩ q2 := by
Contradiction: two distinct triangles in the packing share the edge xd.
Since x and d are distinct and both belong to q₁ ∩ q₂, the intersection has cardinality at least 2. But distinct triangles in the packing Q can share at most 1 vertex, yielding the final contradiction.
uses
Finset.card_le_cardintro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv simp only [Finset.mem_inter] rcases hv with rfl | rfl · exact ⟨hx1a.1,hx2c.1⟩ · exact ⟨hd1,hd2⟩ have hcard := Finset.card_le_card hs have hp := hQpair hq1 hq2 hqne simp [hxd] at hcard omega
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.card_le_three- The cardinality of a set {a, b, c} is at most 3.
Finset.mem_filter.mpr- An element belongs to filter p s if it belongs to s and satisfies property p.
Finset.mem_filter.mp- If an element belongs to filter p s, then it belongs to s and satisfies property p.
SimpleGraph.mem_edgeFinset.mpr- An edge belongs to edgeFinset if it belongs to edgeSet.
SimpleGraph.mem_edgeFinset.mp- If an edge belongs to edgeFinset, then it belongs to edgeSet.
Sym2.eq_iff- Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
SimpleGraph.deleteEdges_le- Deleting a set of edges from a graph results in a subgraph of the original graph.
Finset.card_le_univ- The cardinality of any finite set is at most the cardinality of the ambient finite type.
Nat.sSup_mem- A nonempty, bounded-above set of natural numbers contains its supremum.
simple_graph_maximum_triangle_packing_edge_meets- In a finite graph, every triangle shares at least two vertices with some triangle in any maximum triangle packing.
SimpleGraph.deleteEdges_adj.mp- If an edge exists after deleting a set of edges, it existed in the original graph and was not among the deleted edges.
in693_cycle_third- A set of cardinality 3 containing two elements a and x contains a third element distinct from both.
Ne.symm- If a ≠ b, then b ≠ a.
in693_cycle_two_of_three- If a set contains at least two elements of {a, b, x}, it contains at least one of the pairs {a, b}, {a, x}, or {b, x}.
False.elim- From False, any proposition follows.
Finset.card_le_one.mpr- A finite set has cardinality at most 1 if all pairs of its elements are equal.
Finset.mem_inter- An element belongs to the intersection of two sets if and only if it belongs to both.
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 {a} if and only if it equals a.
not_exists- Negation of an existential quantifier is equivalent to a universal negation.
not_and- Negation of a conjunction a ∧ b is equivalent to a → ¬b.
Finset.card_le_two- The cardinality of a pair {a, b} is at most 2.
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 3000000private theorem in693_cycle_two_of_three {V : Type*} [DecidableEq V] (s : Finset V) (a b x : V) (h : 2 ≤ (s ∩ {a,b,x}).card) : (a ∈ s ∧ b ∈ s) ∨ (a ∈ s ∧ x ∈ s) ∨ (b ∈ s ∧ x ∈ s) := by classical by_contra hn have hle : (s ∩ {a,b,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro u hu v hv simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hu hv aesop omegaprivate theorem in693_cycle_third {V : Type*} [DecidableEq V] (s : Finset V) (a x : V) (hcard : s.card = 3) (ha : a ∈ s) (hx : x ∈ s) : ∃ y ∈ s, y ≠ a ∧ y ≠ x := by classical by_contra hn have hsub : s ⊆ {a,x} := by intro y hy simp only [not_exists, not_and] at hn simp only [Finset.mem_insert, Finset.mem_singleton] by_contra hn2 exact hn y hy (by aesop) (by aesop) have hc := Finset.card_le_card hsub have htwo := Finset.card_le_two (a := a) (b := x) omegatheorem simple_graph_pair_stable_vertex_link_not_four_cycle (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) (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 d : Fin n) (hdist : ({a,b,c,d} : Finset (Fin n)).card = 4) : (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)) ≠ ({s(a,b),s(b,c),s(c,d),s(d,a)} : Finset (Sym2 (Fin n))) := by classical intro hlinkeq have hab : a ≠ b := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,c,d} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := c) (c := d) omega have hac : a ≠ c := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,d} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := d) omega have had : a ≠ d := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) omega have hbc : b ≠ c := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,d} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := d) omega have hbd : b ≠ d := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) omega have hcd : c ≠ d := by intro h have hs : ({a,b,c,d} : Finset (Fin n)) ⊆ {a,b,c} := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv ⊢ aesop have hc := Finset.card_le_card hs have hb := Finset.card_le_three (a := a) (b := b) (c := c) omega have hlink : ∀ u v, G.Adj x u → G.Adj x v → G.Adj u v → s(u,v) ∈ ({s(a,b),s(b,c),s(c,d),s(d,a)} : Finset (Sym2 (Fin n))) := by intro u v hxu hxv huv have hm : s(u,v) ∈ G.edgeFinset.filter (fun e => ∀ w ∈ e, G.Adj x w) := by apply Finset.mem_filter.mpr constructor · exact SimpleGraph.mem_edgeFinset.mpr huv · intro w hw have hw' : w = u ∨ w = v := by simpa using hw rcases hw' with rfl | rfl <;> assumption rwa [hlinkeq] at hm have hE : ∀ u v, s(u,v) ∈ ({s(a,b),s(b,c),s(c,d),s(d,a)} : Finset (Sym2 (Fin n))) → G.Adj u v ∧ G.Adj x u ∧ G.Adj x v := by intro u v h have hm : s(u,v) ∈ G.edgeFinset.filter (fun e => ∀ w ∈ e, G.Adj x w) := by rwa [hlinkeq] obtain ⟨he,hx⟩ := Finset.mem_filter.mp hm exact ⟨SimpleGraph.mem_edgeFinset.mp he, hx u (by simp), hx v (by simp)⟩ have habg := hE a b (by simp) have hbcg := hE b c (by simp) have hcdg := hE c d (by simp) have hdag := hE d a (by simp) have hxa : x ≠ a := habg.2.1.ne have hxb : x ≠ b := habg.2.2.ne have hxc : x ≠ c := hbcg.2.2.ne have hxd : x ≠ d := hcdg.2.2.ne have he : s(a,b) ∈ G.edgeSet := habg.1 have hf : s(b,c) ∈ G.edgeSet := hbcg.1 have hef : s(a,b) ≠ s(b,c) := by simp [Sym2.eq_iff, hab, hbc, hac] let H := G.deleteEdges {s(a,b), s(b,c)} have hHG : H ≤ G := SimpleGraph.deleteEdges_le (G := G) {s(a,b), s(b,c)} 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 have hs := hstable s(a,b) s(b,c) he hf hef change simple_graph_triangle_packing_number H = simple_graph_triangle_packing_number G at hs omega have hQG : ∀ t ∈ Q, G.IsNClique 3 t := by intro t ht; exact (hQH t ht).mono hHG have hQc := simple_graph_maximum_triangle_packing_edge_meets G Q hQG hQpair hQcard' have havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (b ∈ t ∧ c ∈ t) := by intro t ht constructor · intro h have hadj : H.Adj a b := (hQH t ht).isClique h.1 h.2 hab exact (SimpleGraph.deleteEdges_adj.mp hadj).2 (by simp) · intro h have hadj : H.Adj b c := (hQH t ht).isClique h.1 h.2 hbc exact (SimpleGraph.deleteEdges_adj.mp hadj).2 (by simp) have hextract : ∀ q ∈ Q, ∀ v, x ∈ q → v ∈ q → v ≠ x → ∃ u ∈ q, u ≠ v ∧ u ≠ x ∧ G.Adj x u ∧ H.Adj v u := by intro q hq v hxq hvq hvx have hqcl := hQG q hq obtain ⟨u,huq,huv,hux⟩ := in693_cycle_third q v x hqcl.card_eq hvq hxq exact ⟨u,huq,huv,hux,hqcl.isClique hxq huq (Ne.symm hux), (hQH q hq).isClique hvq huq (Ne.symm huv)⟩ have hno_b : ∀ q ∈ Q, ¬ (x ∈ q ∧ b ∈ q) := by intro q hq h obtain ⟨u,huq,hub,hux,hxu,hbu⟩ := hextract q hq b h.1 h.2 (Ne.symm hxb) have hm := hlink b u habg.2.2 hxu (hHG hbu) simp only [Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] at hm have hu : u = a ∨ u = c := by aesop have hn := (SimpleGraph.deleteEdges_adj.mp hbu).2 rcases hu with rfl | rfl · apply hn; simp [Sym2.eq_iff] · apply hn; simp have hba : G.Adj b a := habg.1.symm have hay : G.Adj a x := habg.2.1.symm have hby : G.Adj b x := habg.2.2.symm have hcb : G.Adj c b := hbcg.1.symm have hcy : G.Adj c x := hbcg.2.2.symm have htri1 : G.IsNClique 3 ({x,a,b} : Finset (Fin n)) := by constructor · intro u hu v hv huv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> aesop · simp [hxa,hxb,hab,Ne.symm hxa,Ne.symm hxb,Ne.symm hab] have htri2 : G.IsNClique 3 ({x,b,c} : Finset (Fin n)) := by constructor · intro u hu v hv huv simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl <;> aesop · simp [hxb,hxc,hbc,Ne.symm hxb,Ne.symm hxc,Ne.symm hbc] obtain ⟨q1,hq1,hm1⟩ := hQc {x,a,b} htri1 obtain ⟨q2,hq2,hm2⟩ := hQc {x,b,c} htri2 have hx1a : x ∈ q1 ∧ a ∈ q1 := by rcases in693_cycle_two_of_three q1 x a b hm1 with h | h | h · exact h · exact False.elim (hno_b q1 hq1 h) · exact False.elim ((havoid q1 hq1).1 h) have hx2c : x ∈ q2 ∧ c ∈ q2 := by rcases in693_cycle_two_of_three q2 x b c hm2 with h | h | h · exact False.elim (hno_b q2 hq2 h) · exact h · exact False.elim ((havoid q2 hq2).2 h) have hd1 : d ∈ q1 := by obtain ⟨u,huq,hua,hux,hxu,hau⟩ := hextract q1 hq1 a hx1a.1 hx1a.2 (Ne.symm hxa) have hm := hlink a u habg.2.1 hxu (hHG hau) simp only [Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] at hm have hu : u = b ∨ u = d := by aesop rcases hu with rfl | rfl · exact False.elim ((havoid q1 hq1).1 ⟨hx1a.2,huq⟩) · exact huq have hd2 : d ∈ q2 := by obtain ⟨u,huq,huc,hux,hxu,hcu⟩ := hextract q2 hq2 c hx2c.1 hx2c.2 (Ne.symm hxc) have hm := hlink c u hbcg.2.2 hxu (hHG hcu) simp only [Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] at hm have hu : u = b ∨ u = d := by aesop rcases hu with rfl | rfl · exact False.elim ((havoid q2 hq2).2 ⟨huq,hx2c.2⟩) · exact huq have hqne : q1 ≠ q2 := by intro h; subst q2 have hs : ({x,a,c,d} : Finset (Fin n)) ⊆ q1 := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl | rfl · exact hx1a.1 · exact hx1a.2 · exact hx2c.2 · exact hd1 have hcard := Finset.card_le_card hs have hfour : ({x,a,c,d} : Finset (Fin n)).card = 4 := by simp [hxa,hxc,hxd,hac,had,hcd,Ne.symm hxa,Ne.symm hxc,Ne.symm hxd,Ne.symm hac,Ne.symm had,Ne.symm hcd] have hc := (hQG q1 hq1).card_eq omega have hs : ({x,d} : Finset (Fin n)) ⊆ q1 ∩ q2 := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv simp only [Finset.mem_inter] rcases hv with rfl | rfl · exact ⟨hx1a.1,hx2c.1⟩ · exact ⟨hd1,hd2⟩ have hcard := Finset.card_le_card hs have hp := hQpair hq1 hq2 hqne simp [hxd] at hcard omega