simple_graph_pair_stable_active_vertex_at_least_five_triangles
In a finite graph whose maximum triangle-packing number survives every two-edge deletion, any vertex that lies in a triangle lies in at least five distinct triangles.
Statement
theorem simple_graph_pair_stable_active_vertex_at_least_five_triangles (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) (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ x ∈ t) : 5 ≤ (((Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ x ∈ t)).card)
- Source
- Two-edge-stable triangle-packing residual; exhaustive link audit experiment 20286. No novelty claim.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_pair_stable_vertex_link_edge_spoke_exchangeIn a two-edge-stable graph, for every edge yz of the link at x and every neighbor w of x, another link edge meets yz and avoids w.
- simple_graph_pair_stable_vertex_link_not_four_cycleIn a two-edge-stable graph, the graph induced by the neighborhood of any vertex cannot be exactly a four-cycle after isolated vertices are…
- 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).
- Used by 1
- simple_graph_pair_stable_outside_kernel_five_trianglesIn a two-edge-stable graph, every active vertex that lies in the support-plus-one-vertex kernel and outside a maximum packing supported in…
The proof, explained
The theorem is proved by analyzing the link of an active vertex x, which is the subgraph induced by edges between neighbors of x. Each link edge corresponds bijectively to a triangle containing x, so it suffices to show that the link has at least 5 edges. Under the assumption that the link has at most 4 edges, stability of the triangle-packing number under 2-edge deletions ensures that every link vertex has degree at least 2, forcing the link to contain either a triangle, a 4-cycle, or at least 5 edges. Triangles with additional edges force 5 edges, and 4-cycles are ruled out by a known pair-stability theorem, completing the proof by contradiction.
An edge belongs to the link of x if and only if its endpoints are adjacent to each other and both are adjacent to x.
Unfolding the definition of the filtered edge set and edge membership for unordered pairs in Sym2.
uses
SimpleGraph.mem_edgeSet,Sym2.ballsimp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset] rw [SimpleGraph.mem_edgeSet, Sym2.ball]
Given a triangle on x, y, z and a neighbor w of x, there exists an edge in the link of x sharing a vertex with {y, z}, avoiding w, and distinct from yz.
Applies the spoke exchange theorem simple_graph_pair_stable_vertex_link_edge_spoke_exchange and rewrites the resulting edge into the link set.
uses
simple_graph_pair_stable_vertex_link_edge_spoke_exchange,simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iffobtain ⟨u, v, hxu, hxv, huv, hmem, huw, hvw, hne⟩ := simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G x hstable y z w hy hz hyz hw refine ⟨u, v, ?_, hmem, huw, hvw, hne⟩ rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩
For every edge yz in the link of x, y has a neighbor a distinct from z in the link of x.
Applies the exchange lemma with w = z. The resulting link edge must meet {y, z} but cannot contain z, so it must be incident to y, providing a neighbor a ≠ z.
uses
simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem,Sym2.eq_swapobtain ⟨u, v, hmemE, hex, huz, hvz, hne⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem n G x hstable y z z hy hz hyz hz rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] at hmemE obtain ⟨huv, hxu, hxv⟩ := hmemE rcases hex with huy | huz' | hvy | hvz' · refine ⟨v, by simpa [huy] using huv, hxv, hvz, ?_⟩ rw [show s(y,v) = s(u,v) by rw [huy], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · exact absurd huz' huz · refine ⟨u, by simpa [hvy] using huv.symm, hxu, huz, ?_⟩ rw [show s(y,u) = s(u,v) by rw [hvy, Sym2.eq_swap], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · exact absurd hvz' hvz
For every edge yz in the link of x, z has a neighbor b distinct from y in the link of x.
Symmetrically applies the exchange lemma with w = y, showing that the resulting link edge must be incident to z, providing a neighbor b ≠ y.
uses
simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem,Sym2.eq_swapobtain ⟨u, v, hmemE, hex, huy, hvy, hne⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem n G x hstable y z y hy hz hyz hy rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] at hmemE obtain ⟨huv, hxu, hxv⟩ := hmemE rcases hex with huz | huz' | hvz | hvz' · exact absurd huz huy · refine ⟨v, by simpa [huz'] using huv, hxv, hvy, ?_⟩ rw [show s(z,v) = s(u,v) by rw [huz'], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · exact absurd hvz hvy · refine ⟨u, by simpa [hvz'] using huv.symm, hxu, huy, ?_⟩ rw [show s(z,u) = s(u,v) by rw [hvz', Sym2.eq_swap], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩
If x belongs to a triangle, then its link contains at least one edge.
Since x belongs to a 3-clique {a, b, c}, the other two vertices form an edge in the link of x.
uses
SimpleGraph.is3Clique_iffobtain ⟨t, ht, hxt⟩ := hactive rw [SimpleGraph.is3Clique_iff] at ht obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := ht simp only [Finset.mem_insert, Finset.mem_singleton] at hxt rcases hxt with rfl | rfl | rfl · exact ⟨b, c, hab, hac, hbc, by rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hbc, hab, hac⟩⟩ · exact ⟨a, c, hab.symm, hbc, hac, by rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hac, hab.symm, hbc⟩⟩ · exact ⟨a, b, hac.symm, hbc.symm, hab, by rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hab, hac.symm, hbc.symm⟩⟩
A set of 4 edges in the link together with an external link edge implies the link has at least 5 edges.
Adding an element not in a set of size 4 produces a subset of size 5 of the link edges.
uses
Finset.card_insert_of_notMem,Finset.card_le_cardhave hcard : (insert g T).card = 5 := by rw [Finset.card_insert_of_notMem hgT, hT4] have hsub : insert g T ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by intro e he rw [Finset.mem_insert] at he rcases he with rfl | h · exact hgE · exact hTsub h calc 5 = (insert g T).card := hcard.symm _ ≤ _ := Finset.card_le_card hsub
If the link contains a triangle and an edge g outside it, one endpoint u of g lies outside the triangle and has another neighbor u2 in the link.
The external edge g cannot have both endpoints in {y, z, p}. Orienting it so that u ∉ {y, z, p} and applying the left-neighbor lemma gives another link edge uu2 incident to u.
uses
Sym2.ind,simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_lefthave hyp' : y ≠ p := hyp.ne have hzp' : z ≠ p := hzp.ne have hyz' : y ≠ z := hyz.ne have hgnd : ¬ g.IsDiag := G.not_isDiag_of_mem_edgeFinset (Finset.mem_filter.mp hgE).1 obtain ⟨r, s, hg_eq⟩ : ∃ r s, g = s(r,s) := by induction g using Sym2.ind with | _ r s => exact ⟨r, s, rfl⟩ subst hg_eq rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] at hgE obtain ⟨hrs, hxr, hxs⟩ := hgE have hrne : r ≠ s := hrs.ne have hout : r ∉ ({y,z,p} : Finset (Fin n)) ∨ s ∉ ({y,z,p} : Finset (Fin n)) := by by_contra h push Not at h obtain ⟨hr, hs⟩ := h simp only [Finset.mem_insert, Finset.mem_singleton] at hr hs hgT rcases hr with rfl | rfl | rfl <;> rcases hs with rfl | rfl | rfl all_goals first | exact absurd rfl hrne | exact hgT (by simp) obtain ⟨u, v, hg_eq2, huv, hxu, hxv, huout, huv_ne⟩ : ∃ u v, s(u,v) = s(r,s) ∧ G.Adj u v ∧ G.Adj x u ∧ G.Adj x v ∧ u ∉ ({y,z,p} : Finset (Fin n)) ∧ u ≠ v := by rcases hout with hr | hs · exact ⟨r, s, rfl, hrs, hxr, hxs, hr, hrne⟩ · exact ⟨s, r, by rw [Sym2.eq_swap], hrs.symm, hxs, hxr, hs, hrne.symm⟩ obtain ⟨u2, huu2, hxu2, hu2v, hu2E⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable u v hxu hxv huv
A triangle in the link plus an edge outside the triangle implies the link has at least 5 edges.
The 3 edges of the triangle, together with uv and uu2, form a set of 5 pairwise distinct edges in the link.
uses
Finset.card_insert_of_notMem,Finset.card_le_cardset T : Finset (Sym2 (Fin n)) := {s(y,z), s(y,p), s(z,p)} with hTdef have hTsub : T ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by intro e he simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hyz, hy, hz⟩ · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hyp, hy, hp⟩ · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hzp, hz, hp⟩ have hTcard : T.card = 3 := by rw [hTdef] rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [hyp', hzp', hyz'] have hg'ne : s(u,u2) ∉ T := by intro hmem simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at hmem have hu : u ∈ s(u,u2) := Sym2.mem_mk_left u u2 rcases hmem with hmem | hmem | hmem all_goals rw [hmem] at hu simp only [Sym2.mem_iff, Finset.mem_insert, Finset.mem_singleton] at hu exact huout (by rcases hu with h|h <;> simp [h]) have hgg' : s(u,u2) ≠ s(u,v) := by intro h rw [Sym2.eq_iff] at h rcases h with ⟨-, h2⟩ | ⟨h1, -⟩ · exact hu2v h2 · exact huv_ne h1 have hgT' : s(u,v) ∉ T := by rw [hg_eq2]; exact hgT have hgin : s(u,v) ∉ insert s(u,u2) T := by intro h rw [Finset.mem_insert] at h rcases h with h | h · exact hgg' h.symm · exact hgT' h have hcard5 : (insert s(u,v) (insert s(u,u2) T)).card = 5 := by rw [Finset.card_insert_of_notMem hgin, Finset.card_insert_of_notMem hg'ne, hTcard] have hsub : insert s(u,v) (insert s(u,u2) T) ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by intro e he rw [Finset.mem_insert, Finset.mem_insert] at he rcases he with rfl | rfl | hT · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huu2, hxu, hxu2⟩ · exact hTsub hT calc 5 = (insert s(u,v) (insert s(u,u2) T)).card := hcard5.symm _ ≤ _ := Finset.card_le_card hsub
Assuming the link has at most 4 edges, an initial link edge yz exists with adjacent link edges yp and zq.
The active vertex x provides an initial link edge yz, and the left and right neighbor lemmas provide additional neighbors p ≠ z and q ≠ y in the link.
uses
simple_graph_pair_stable_active_vertex_at_least_five_triangles_active_link_edge,simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left,simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_rightlet E : Finset (Sym2 (Fin n)) := G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) change 5 ≤ E.card by_contra hgoal have hle : E.card ≤ 4 := by omega obtain ⟨y, z, hy, hz, hyz, hyzE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_active_link_edge n G x hactive obtain ⟨p, hyp, hxp, hpz, hypE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable y z hy hz hyz obtain ⟨q, hzq, hxq, hqy, hzqE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_right n G x hstable y z hy hz hyz have hpy : p ≠ y := hyp.ne.symm have hqz : q ≠ z := hzq.ne.symm have hyq : y ≠ q := hqy.symm have hyz_ne : y ≠ z := hyz.ne have hzp : z ≠ p := hpz.symm
The case p = q is impossible. automation
If p = q, the link contains a triangle {yz, yp, zp}. If these are all the link edges, the exchange lemma with spoke xp derives a contradiction; otherwise, an extra edge forces at least 5 edges, closed by linear integer arithmetic.
uses
simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem,simple_graph_pair_stable_active_vertex_at_least_five_triangles_triangle_extra_fiveby_cases hpq : p = q · subst q set T : Finset (Sym2 (Fin n)) := {s(y,z), s(y,p), s(z,p)} with hTdef have hTsub : T ⊆ E := by intro e he simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · exact hyzE · exact hypE · exact hzqE by_cases hsub : E ⊆ T · have hET : E = T := Finset.Subset.antisymm hsub hTsub obtain ⟨u, v, huve, hdisj, hup, hvp, hne⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem n G x hstable y z p hy hz hyz hxp have huve' : s(u,v) ∈ E := huve rw [hET] at huve' simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at huve' rcases huve' with h | h | h · exact hne h · have hpmem : p ∈ s(u,v) := by rw [h]; exact Sym2.mem_mk_right y p simp only [Sym2.mem_iff] at hpmem rcases hpmem with h' | h' · exact hup h'.symm · exact hvp h'.symm · have hpmem : p ∈ s(u,v) := by rw [h]; exact Sym2.mem_mk_right z p simp only [Sym2.mem_iff] at hpmem rcases hpmem with h' | h' · exact hup h'.symm · exact hvp h'.symm · obtain ⟨g, hgE, hgT⟩ := Finset.not_subset.mp hsub have h5 : 5 ≤ E.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles_triangle_extra_five n G x hstable y z p hy hz hxp hyz hyp hzq g hgE hgT omega
The case p ≠ q and r = q is impossible.
When p ≠ q, applying the left-neighbor lemma to py gives a neighbor r ≠ y of p. If r = q, the link would equal a 4-cycle, contradicting the forbidden 4-cycle lemma for pair-stable graphs.
uses
simple_graph_pair_stable_vertex_link_not_four_cycle· have hpq' : p ≠ q := hpq obtain ⟨r, hpr, hxr, hry, hprE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable p y hxp hy hyp.symm by_cases hrq : r = q · subst r set T4 : Finset (Sym2 (Fin n)) := {s(y,z), s(z,q), s(q,p), s(p,y)} with hT4def have hT4sub : T4 ⊆ E := by intro e he simp only [hT4def, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl · exact hyzE · exact hzqE · rw [Sym2.eq_swap]; exact hprE · rw [Sym2.eq_swap]; exact hypE have hT4card : T4.card = 4 := by rw [hT4def] rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [Sym2.eq_iff, hyz_ne, hqz, hpq', hpy, hyq, hzp, hyz_ne.symm, hqz.symm, hpq'.symm, hpy.symm, hyq.symm, hzp.symm] have hET4 : E = T4 := (Finset.eq_of_subset_of_card_le hT4sub (by omega)).symm have hcard4 : ({y,z,q,p} : Finset (Fin n)).card = 4 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [hyz_ne, hyq, hyp.ne, hqz, hzp, hpq', hyz_ne.symm, hyq.symm, hyp.ne.symm, hqz.symm, hzp.symm, hpq'.symm] have hneq := simple_graph_pair_stable_vertex_link_not_four_cycle n G x hstable y z q p hcard4 apply hneq simpa only [hT4def] using hET4
The case p ≠ q and r ≠ q is impossible, establishing that the link of x has at least 5 edges. automation
If r ≠ q, the four edges {yz, yp, zq, pr} are distinct. Applying the neighbor lemma to qz provides a 5th edge qb in the link, which contradicts the assumption of at most 4 edges via linear integer arithmetic.
uses
simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left,simple_graph_pair_stable_active_vertex_at_least_five_triangles_five_of_four· have hrq' : r ≠ q := hrq set T4 : Finset (Sym2 (Fin n)) := {s(y,z), s(y,p), s(z,q), s(p,r)} with hT4def have hT4sub : T4 ⊆ E := by intro e he simp only [hT4def, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl · exact hyzE · exact hypE · exact hzqE · exact hprE have hT4card : T4.card = 4 := by rw [hT4def] rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [Sym2.eq_iff, hyz_ne, hyp.ne, hqz, hry, hpq', hpz, hyq, hyz_ne.symm, hyp.ne.symm, hqz.symm, hry.symm, hpq'.symm, hpz.symm, hyq.symm] obtain ⟨b, hqb, hxb, hbz, hqbE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable q z hxq hz hzq.symm have hgqT : s(q,b) ∉ T4 := by intro hmem simp only [hT4def, Finset.mem_insert, Finset.mem_singleton] at hmem rcases hmem with h | h | h | h · have hqm : q ∈ s(y,z) := by rw [← h]; exact Sym2.mem_mk_left q b simp only [Sym2.mem_iff] at hqm rcases hqm with h' | h' · exact hqy h' · exact hqz h' · have hqm : q ∈ s(y,p) := by rw [← h]; exact Sym2.mem_mk_left q b simp only [Sym2.mem_iff] at hqm rcases hqm with h' | h' · exact hqy h' · exact hpq' h'.symm · have hbm : b ∈ s(z,q) := by rw [← h]; exact Sym2.mem_mk_right q b simp only [Sym2.mem_iff] at hbm rcases hbm with h' | h' · exact hbz h' · exact hqb.ne.symm h' · have hqm : q ∈ s(p,r) := by rw [← h]; exact Sym2.mem_mk_left q b simp only [Sym2.mem_iff] at hqm rcases hqm with h' | h' · exact hpq' h'.symm · exact hrq' h'.symm have h5 : 5 ≤ E.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles_five_of_four n G x T4 (s(q,b)) hT4card hT4sub hqbE hgqT omega
Mapping each link edge {r, s} to {x, r, s} defines a map into the triangles containing x.
Since r and s are adjacent to each other and both are adjacent to x, {x, r, s} forms a 3-clique containing x.
uses
Finset.card_le_card_of_injOn,SimpleGraph.is3Clique_triple_ifflet T : Finset (Finset (Fin n)) := (Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ x ∈ t) change E.card ≤ T.card apply Finset.card_le_card_of_injOn (fun e : Sym2 (Fin n) => insert x e.toFinset) · intro e he have heE : e ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := he obtain ⟨r, s, heq⟩ : ∃ r s, e = s(r,s) := by induction e using Sym2.ind with | _ r s => exact ⟨r, s, rfl⟩ subst heq obtain ⟨hrs, hxr, hxs⟩ := (simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff n G x r s).mp heE change insert x (s(r,s)).toFinset ∈ T simp only [T, Finset.mem_filter, Finset.mem_univ, true_and] constructor · have hxf : insert x (s(r,s)).toFinset = {x, r, s} := by rw [Sym2.toFinset_mk_eq] rw [hxf, SimpleGraph.is3Clique_triple_iff] exact ⟨hxr, hxs, hrs⟩ · exact Finset.mem_insert_self x _
The map from link edges to triangles containing x is injective, so the number of link edges is at most the number of triangles containing x.
Because x cannot be an endpoint of an edge in its own link, removing x from {x, r, s} uniquely recovers the unordered pair {r, s}.
uses
Finset.erase_insert,Sym2.ext· intro e1 he1 e2 he2 h have he1E : e1 ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := he1 have he2E : e2 ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := he2 have hx1 : x ∉ e1.toFinset := by intro hx have hx' : x ∈ e1 := Sym2.mem_toFinset.mp hx exact ((Finset.mem_filter.mp he1E).2 x hx').ne rfl have hx2 : x ∉ e2.toFinset := by intro hx have hx' : x ∈ e2 := Sym2.mem_toFinset.mp hx exact ((Finset.mem_filter.mp he2E).2 x hx').ne rfl have hto : e1.toFinset = e2.toFinset := by have hcongr := congrArg (fun t : Finset (Fin n) => t.erase x) h rw [Finset.erase_insert hx1, Finset.erase_insert hx2] at hcongr exact hcongr exact Sym2.ext (fun y => by rw [← Sym2.mem_toFinset, hto, Sym2.mem_toFinset])
Any active vertex in a 2-edge deletion stable graph lies in at least five triangles. automation
Combining the lower bound of 5 edges in the link of x with the injection into triangles containing x closes the goal by linear integer arithmetic.
uses
simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_card_ge_five,simple_graph_pair_stable_active_vertex_at_least_five_triangles_edge_card_le_triangle_cardhave hE5 : 5 ≤ (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)).card := simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_card_ge_five n G x hstable hactive have hle := simple_graph_pair_stable_active_vertex_at_least_five_triangles_edge_card_le_triangle_card n G x omega
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) belongs to the edge set of a simple graph if and only if v and w are adjacent.
Sym2.ball- A property holds for all elements of the unordered pair s(a, b) if and only if it holds for both a and b.
simple_graph_pair_stable_vertex_link_edge_spoke_exchange- In a 2-edge deletion stable graph, given a triangle on x, y, z and a neighbor w of x, there exists a link edge uv meeting {y, z}, disjoint from w, and distinct from yz.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff- An unordered pair s(a, b) belongs to the link of x if and only if a and b are adjacent and both are adjacent to x.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem- Formulates the spoke-exchange theorem in terms of membership in the link edge set of x.
Sym2.eq_swap- The unordered pair s(a, b) is equal to s(b, a).
SimpleGraph.is3Clique_iff- A finite set of vertices is a 3-clique if and only if it consists of three mutually adjacent vertices.
Finset.card_insert_of_notMem- Inserting an element into a finite set that does not contain it increments the cardinality by 1.
Finset.card_le_card- If s is a subset of t, the cardinality of s is at most that of t.
Sym2.ind- Every unordered pair in Sym2 is of the form s(r, s) for some r and s.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left- For every edge yz in the link of x, vertex y has another neighbor a distinct from z in the link of x.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_active_link_edge- If x belongs to a triangle, there is at least one edge in the link of x.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_right- For every edge yz in the link of x, vertex z has another neighbor b distinct from y in the link of x.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_triangle_extra_five- If the link of x contains a triangle and an additional edge outside it, then the link contains at least 5 edges.
simple_graph_pair_stable_vertex_link_not_four_cycle- In a 2-edge deletion stable graph, the link of a vertex cannot be an induced 4-cycle.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_five_of_four- If the link contains a set of 4 edges and an additional edge not in that set, it has at least 5 edges.
Finset.card_le_card_of_injOn- An injective map between finite sets implies the cardinality of the domain is at most the cardinality of the codomain.
SimpleGraph.is3Clique_triple_iff- The set {a, b, c} is a 3-clique if and only if a, b, and c are mutually adjacent.
Finset.erase_insert- Erasing an element from an inserted set recovers the original set if the element was not already present.
Sym2.ext- Two unordered pairs in Sym2 are equal if and only if they have the same elements.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_card_ge_five- If an active vertex x lies in a 2-edge deletion stable graph, the link of x contains at least 5 edges.
simple_graph_pair_stable_active_vertex_at_least_five_triangles_edge_card_le_triangle_card- The number of edges in the link of x is at most the number of triangles containing x.
- Unresolved check: no step explains line(s) 345 -- every tactic of the proof has to belong to some step
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 Sym2private lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x a b : Fin n) : s(a,b) ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) ↔ G.Adj a b ∧ G.Adj x a ∧ G.Adj x b := by simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset] rw [SimpleGraph.mem_edgeSet, Sym2.ball]private lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem (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) (y z w : Fin n) (hy : G.Adj x y) (hz : G.Adj x z) (hyz : G.Adj y z) (hw : G.Adj x w) : ∃ u v, s(u,v) ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) ∧ (u = y ∨ u = z ∨ v = y ∨ v = z) ∧ u ≠ w ∧ v ≠ w ∧ s(u,v) ≠ s(y,z) := by obtain ⟨u, v, hxu, hxv, huv, hmem, huw, hvw, hne⟩ := simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G x hstable y z w hy hz hyz hw refine ⟨u, v, ?_, hmem, huw, hvw, hne⟩ rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩private lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left (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) (y z : Fin n) (hy : G.Adj x y) (hz : G.Adj x z) (hyz : G.Adj y z) : ∃ a, G.Adj y a ∧ G.Adj x a ∧ a ≠ z ∧ s(y,a) ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by obtain ⟨u, v, hmemE, hex, huz, hvz, hne⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem n G x hstable y z z hy hz hyz hz rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] at hmemE obtain ⟨huv, hxu, hxv⟩ := hmemE rcases hex with huy | huz' | hvy | hvz' · refine ⟨v, by simpa [huy] using huv, hxv, hvz, ?_⟩ rw [show s(y,v) = s(u,v) by rw [huy], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · exact absurd huz' huz · refine ⟨u, by simpa [hvy] using huv.symm, hxu, huz, ?_⟩ rw [show s(y,u) = s(u,v) by rw [hvy, Sym2.eq_swap], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · exact absurd hvz' hvzprivate lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_right (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) (y z : Fin n) (hy : G.Adj x y) (hz : G.Adj x z) (hyz : G.Adj y z) : ∃ b, G.Adj z b ∧ G.Adj x b ∧ b ≠ y ∧ s(z,b) ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by obtain ⟨u, v, hmemE, hex, huy, hvy, hne⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem n G x hstable y z y hy hz hyz hy rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] at hmemE obtain ⟨huv, hxu, hxv⟩ := hmemE rcases hex with huz | huz' | hvz | hvz' · exact absurd huz huy · refine ⟨v, by simpa [huz'] using huv, hxv, hvy, ?_⟩ rw [show s(z,v) = s(u,v) by rw [huz'], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · exact absurd hvz hvy · refine ⟨u, by simpa [hvz'] using huv.symm, hxu, huy, ?_⟩ rw [show s(z,u) = s(u,v) by rw [hvz', Sym2.eq_swap], simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩private lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_active_link_edge (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ x ∈ t) : ∃ y z, G.Adj x y ∧ G.Adj x z ∧ G.Adj y z ∧ s(y,z) ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by obtain ⟨t, ht, hxt⟩ := hactive rw [SimpleGraph.is3Clique_iff] at ht obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := ht simp only [Finset.mem_insert, Finset.mem_singleton] at hxt rcases hxt with rfl | rfl | rfl · exact ⟨b, c, hab, hac, hbc, by rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hbc, hab, hac⟩⟩ · exact ⟨a, c, hab.symm, hbc, hac, by rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hac, hab.symm, hbc⟩⟩ · exact ⟨a, b, hac.symm, hbc.symm, hab, by rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hab, hac.symm, hbc.symm⟩⟩private lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_five_of_four (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) (T : Finset (Sym2 (Fin n))) (g : Sym2 (Fin n)) (hT4 : T.card = 4) (hTsub : T ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)) (hgE : g ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)) (hgT : g ∉ T) : 5 ≤ (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)).card := by have hcard : (insert g T).card = 5 := by rw [Finset.card_insert_of_notMem hgT, hT4] have hsub : insert g T ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by intro e he rw [Finset.mem_insert] at he rcases he with rfl | h · exact hgE · exact hTsub h calc 5 = (insert g T).card := hcard.symm _ ≤ _ := Finset.card_le_card hsubprivate lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_triangle_extra_five (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) (y z p : Fin n) (hy : G.Adj x y) (hz : G.Adj x z) (hp : G.Adj x p) (hyz : G.Adj y z) (hyp : G.Adj y p) (hzp : G.Adj z p) (g : Sym2 (Fin n)) (hgE : g ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)) (hgT : g ∉ ({s(y,z), s(y,p), s(z,p)} : Finset (Sym2 (Fin n)))) : 5 ≤ (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)).card := by have hyp' : y ≠ p := hyp.ne have hzp' : z ≠ p := hzp.ne have hyz' : y ≠ z := hyz.ne have hgnd : ¬ g.IsDiag := G.not_isDiag_of_mem_edgeFinset (Finset.mem_filter.mp hgE).1 obtain ⟨r, s, hg_eq⟩ : ∃ r s, g = s(r,s) := by induction g using Sym2.ind with | _ r s => exact ⟨r, s, rfl⟩ subst hg_eq rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] at hgE obtain ⟨hrs, hxr, hxs⟩ := hgE have hrne : r ≠ s := hrs.ne have hout : r ∉ ({y,z,p} : Finset (Fin n)) ∨ s ∉ ({y,z,p} : Finset (Fin n)) := by by_contra h push Not at h obtain ⟨hr, hs⟩ := h simp only [Finset.mem_insert, Finset.mem_singleton] at hr hs hgT rcases hr with rfl | rfl | rfl <;> rcases hs with rfl | rfl | rfl all_goals first | exact absurd rfl hrne | exact hgT (by simp) obtain ⟨u, v, hg_eq2, huv, hxu, hxv, huout, huv_ne⟩ : ∃ u v, s(u,v) = s(r,s) ∧ G.Adj u v ∧ G.Adj x u ∧ G.Adj x v ∧ u ∉ ({y,z,p} : Finset (Fin n)) ∧ u ≠ v := by rcases hout with hr | hs · exact ⟨r, s, rfl, hrs, hxr, hxs, hr, hrne⟩ · exact ⟨s, r, by rw [Sym2.eq_swap], hrs.symm, hxs, hxr, hs, hrne.symm⟩ obtain ⟨u2, huu2, hxu2, hu2v, hu2E⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable u v hxu hxv huv set T : Finset (Sym2 (Fin n)) := {s(y,z), s(y,p), s(z,p)} with hTdef have hTsub : T ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by intro e he simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hyz, hy, hz⟩ · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hyp, hy, hp⟩ · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨hzp, hz, hp⟩ have hTcard : T.card = 3 := by rw [hTdef] rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [hyp', hzp', hyz'] have hg'ne : s(u,u2) ∉ T := by intro hmem simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at hmem have hu : u ∈ s(u,u2) := Sym2.mem_mk_left u u2 rcases hmem with hmem | hmem | hmem all_goals rw [hmem] at hu simp only [Sym2.mem_iff, Finset.mem_insert, Finset.mem_singleton] at hu exact huout (by rcases hu with h|h <;> simp [h]) have hgg' : s(u,u2) ≠ s(u,v) := by intro h rw [Sym2.eq_iff] at h rcases h with ⟨-, h2⟩ | ⟨h1, -⟩ · exact hu2v h2 · exact huv_ne h1 have hgT' : s(u,v) ∉ T := by rw [hg_eq2]; exact hgT have hgin : s(u,v) ∉ insert s(u,u2) T := by intro h rw [Finset.mem_insert] at h rcases h with h | h · exact hgg' h.symm · exact hgT' h have hcard5 : (insert s(u,v) (insert s(u,u2) T)).card = 5 := by rw [Finset.card_insert_of_notMem hgin, Finset.card_insert_of_notMem hg'ne, hTcard] have hsub : insert s(u,v) (insert s(u,u2) T) ⊆ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := by intro e he rw [Finset.mem_insert, Finset.mem_insert] at he rcases he with rfl | rfl | hT · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huv, hxu, hxv⟩ · rw [simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff] exact ⟨huu2, hxu, hxu2⟩ · exact hTsub hT calc 5 = (insert s(u,v) (insert s(u,u2) T)).card := hcard5.symm _ ≤ _ := Finset.card_le_card hsubprivate lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_card_ge_five (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) (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ x ∈ t) : 5 ≤ (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)).card := by let E : Finset (Sym2 (Fin n)) := G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) change 5 ≤ E.card by_contra hgoal have hle : E.card ≤ 4 := by omega obtain ⟨y, z, hy, hz, hyz, hyzE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_active_link_edge n G x hactive obtain ⟨p, hyp, hxp, hpz, hypE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable y z hy hz hyz obtain ⟨q, hzq, hxq, hqy, hzqE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_right n G x hstable y z hy hz hyz have hpy : p ≠ y := hyp.ne.symm have hqz : q ≠ z := hzq.ne.symm have hyq : y ≠ q := hqy.symm have hyz_ne : y ≠ z := hyz.ne have hzp : z ≠ p := hpz.symm by_cases hpq : p = q · subst q set T : Finset (Sym2 (Fin n)) := {s(y,z), s(y,p), s(z,p)} with hTdef have hTsub : T ⊆ E := by intro e he simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl · exact hyzE · exact hypE · exact hzqE by_cases hsub : E ⊆ T · have hET : E = T := Finset.Subset.antisymm hsub hTsub obtain ⟨u, v, huve, hdisj, hup, hvp, hne⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem n G x hstable y z p hy hz hyz hxp have huve' : s(u,v) ∈ E := huve rw [hET] at huve' simp only [hTdef, Finset.mem_insert, Finset.mem_singleton] at huve' rcases huve' with h | h | h · exact hne h · have hpmem : p ∈ s(u,v) := by rw [h]; exact Sym2.mem_mk_right y p simp only [Sym2.mem_iff] at hpmem rcases hpmem with h' | h' · exact hup h'.symm · exact hvp h'.symm · have hpmem : p ∈ s(u,v) := by rw [h]; exact Sym2.mem_mk_right z p simp only [Sym2.mem_iff] at hpmem rcases hpmem with h' | h' · exact hup h'.symm · exact hvp h'.symm · obtain ⟨g, hgE, hgT⟩ := Finset.not_subset.mp hsub have h5 : 5 ≤ E.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles_triangle_extra_five n G x hstable y z p hy hz hxp hyz hyp hzq g hgE hgT omega · have hpq' : p ≠ q := hpq obtain ⟨r, hpr, hxr, hry, hprE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable p y hxp hy hyp.symm by_cases hrq : r = q · subst r set T4 : Finset (Sym2 (Fin n)) := {s(y,z), s(z,q), s(q,p), s(p,y)} with hT4def have hT4sub : T4 ⊆ E := by intro e he simp only [hT4def, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl · exact hyzE · exact hzqE · rw [Sym2.eq_swap]; exact hprE · rw [Sym2.eq_swap]; exact hypE have hT4card : T4.card = 4 := by rw [hT4def] rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [Sym2.eq_iff, hyz_ne, hqz, hpq', hpy, hyq, hzp, hyz_ne.symm, hqz.symm, hpq'.symm, hpy.symm, hyq.symm, hzp.symm] have hET4 : E = T4 := (Finset.eq_of_subset_of_card_le hT4sub (by omega)).symm have hcard4 : ({y,z,q,p} : Finset (Fin n)).card = 4 := by rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [hyz_ne, hyq, hyp.ne, hqz, hzp, hpq', hyz_ne.symm, hyq.symm, hyp.ne.symm, hqz.symm, hzp.symm, hpq'.symm] have hneq := simple_graph_pair_stable_vertex_link_not_four_cycle n G x hstable y z q p hcard4 apply hneq simpa only [hT4def] using hET4 · have hrq' : r ≠ q := hrq set T4 : Finset (Sym2 (Fin n)) := {s(y,z), s(y,p), s(z,q), s(p,r)} with hT4def have hT4sub : T4 ⊆ E := by intro e he simp only [hT4def, Finset.mem_insert, Finset.mem_singleton] at he rcases he with rfl | rfl | rfl | rfl · exact hyzE · exact hypE · exact hzqE · exact hprE have hT4card : T4.card = 4 := by rw [hT4def] rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] all_goals simp [Sym2.eq_iff, hyz_ne, hyp.ne, hqz, hry, hpq', hpz, hyq, hyz_ne.symm, hyp.ne.symm, hqz.symm, hry.symm, hpq'.symm, hpz.symm, hyq.symm] obtain ⟨b, hqb, hxb, hbz, hqbE⟩ := simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left n G x hstable q z hxq hz hzq.symm have hgqT : s(q,b) ∉ T4 := by intro hmem simp only [hT4def, Finset.mem_insert, Finset.mem_singleton] at hmem rcases hmem with h | h | h | h · have hqm : q ∈ s(y,z) := by rw [← h]; exact Sym2.mem_mk_left q b simp only [Sym2.mem_iff] at hqm rcases hqm with h' | h' · exact hqy h' · exact hqz h' · have hqm : q ∈ s(y,p) := by rw [← h]; exact Sym2.mem_mk_left q b simp only [Sym2.mem_iff] at hqm rcases hqm with h' | h' · exact hqy h' · exact hpq' h'.symm · have hbm : b ∈ s(z,q) := by rw [← h]; exact Sym2.mem_mk_right q b simp only [Sym2.mem_iff] at hbm rcases hbm with h' | h' · exact hbz h' · exact hqb.ne.symm h' · have hqm : q ∈ s(p,r) := by rw [← h]; exact Sym2.mem_mk_left q b simp only [Sym2.mem_iff] at hqm rcases hqm with h' | h' · exact hpq' h'.symm · exact hrq' h'.symm have h5 : 5 ≤ E.card := simple_graph_pair_stable_active_vertex_at_least_five_triangles_five_of_four n G x T4 (s(q,b)) hT4card hT4sub hqbE hgqT omegaprivate lemma simple_graph_pair_stable_active_vertex_at_least_five_triangles_edge_card_le_triangle_card (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (x : Fin n) : (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)).card ≤ ((Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ x ∈ t)).card := by let E : Finset (Sym2 (Fin n)) := G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) let T : Finset (Finset (Fin n)) := (Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ x ∈ t) change E.card ≤ T.card apply Finset.card_le_card_of_injOn (fun e : Sym2 (Fin n) => insert x e.toFinset) · intro e he have heE : e ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := he obtain ⟨r, s, heq⟩ : ∃ r s, e = s(r,s) := by induction e using Sym2.ind with | _ r s => exact ⟨r, s, rfl⟩ subst heq obtain ⟨hrs, hxr, hxs⟩ := (simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff n G x r s).mp heE change insert x (s(r,s)).toFinset ∈ T simp only [T, Finset.mem_filter, Finset.mem_univ, true_and] constructor · have hxf : insert x (s(r,s)).toFinset = {x, r, s} := by rw [Sym2.toFinset_mk_eq] rw [hxf, SimpleGraph.is3Clique_triple_iff] exact ⟨hxr, hxs, hrs⟩ · exact Finset.mem_insert_self x _ · intro e1 he1 e2 he2 h have he1E : e1 ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := he1 have he2E : e2 ∈ G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v) := he2 have hx1 : x ∉ e1.toFinset := by intro hx have hx' : x ∈ e1 := Sym2.mem_toFinset.mp hx exact ((Finset.mem_filter.mp he1E).2 x hx').ne rfl have hx2 : x ∉ e2.toFinset := by intro hx have hx' : x ∈ e2 := Sym2.mem_toFinset.mp hx exact ((Finset.mem_filter.mp he2E).2 x hx').ne rfl have hto : e1.toFinset = e2.toFinset := by have hcongr := congrArg (fun t : Finset (Fin n) => t.erase x) h rw [Finset.erase_insert hx1, Finset.erase_insert hx2] at hcongr exact hcongr exact Sym2.ext (fun y => by rw [← Sym2.mem_toFinset, hto, Sym2.mem_toFinset])theorem simple_graph_pair_stable_active_vertex_at_least_five_triangles (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) (hactive : ∃ t : Finset (Fin n), G.IsNClique 3 t ∧ x ∈ t) : 5 ≤ (((Finset.univ : Finset (Finset (Fin n))).filter (fun t => G.IsNClique 3 t ∧ x ∈ t)).card) := by have hE5 : 5 ≤ (G.edgeFinset.filter (fun e => ∀ v ∈ e, G.Adj x v)).card := simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_card_ge_five n G x hstable hactive have hle := simple_graph_pair_stable_active_vertex_at_least_five_triangles_edge_card_le_triangle_card n G x omega