AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_active_vertex_at_least_five_triangles

theoremverified

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
Used by 1

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.

  1. 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.

    lines 7–8

    uses SimpleGraph.mem_edgeSet, Sym2.ball

      simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset]
      rw [SimpleGraph.mem_edgeSet, Sym2.ball]
  2. 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.

    lines 18–22

    uses simple_graph_pair_stable_vertex_link_edge_spoke_exchange, simple_graph_pair_stable_active_vertex_at_least_five_triangles_link_mem_iff

      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⟩
  3. 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.

    lines 32–47

    uses simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem, Sym2.eq_swap

      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' hvz
  4. 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.

    lines 57–72

    uses simple_graph_pair_stable_active_vertex_at_least_five_triangles_exchange_mem, Sym2.eq_swap

      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⟩
  5. 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.

    lines 79–92

    uses SimpleGraph.is3Clique_iff

      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⟩⟩
  6. 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.

    lines 100–110

    uses Finset.card_insert_of_notMem, Finset.card_le_card

      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 hsub
    
  7. 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.

    lines 122–150

    uses Sym2.ind, simple_graph_pair_stable_active_vertex_at_least_five_triangles_other_edge_left

      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
  8. 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.

    lines 151–202

    uses Finset.card_insert_of_notMem, Finset.card_le_card

      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 hsub
  9. 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.

    lines 211–227

    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_right

      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
  10. 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.

    lines 228–262

    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_five

      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
  11. 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.

    lines 263–292

    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
  12. 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.

    lines 293–340

    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
    
  13. 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.

    lines 346–365

    uses Finset.card_le_card_of_injOn, SimpleGraph.is3Clique_triple_iff

      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 _
  14. 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}.

    lines 366–383

    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])
    
  15. 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.

    lines 385–391

    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_card

      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
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.

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 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
See it in the graphDiscuss this resultChallenge it