AFTD Auto-Formalizing Theoretical Domains

simple_graph_pair_stable_vertex_link_not_four_cycle

theoremverified

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

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.

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

    lines 8–15

    uses Finset.card_le_one.mpr, Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton

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

    lines 20–30

    uses not_exists, not_and, Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_le_two

      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)
      omega
  3. 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)}.

    lines 33–34

      classical
      intro hlinkeq
  4. The 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.

    lines 35–88

    uses Finset.card_le_card, Finset.card_le_three

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

    lines 89–116

    uses Finset.mem_filter.mpr, SimpleGraph.mem_edgeFinset.mpr, Finset.mem_filter.mp, SimpleGraph.mem_edgeFinset.mp, Sym2.eq_iff

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

    lines 117–135

    uses SimpleGraph.deleteEdges_le, Finset.card_le_univ, Nat.sSup_mem, simple_graph_maximum_triangle_packing_edge_meets

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

    lines 136–152

    uses SimpleGraph.deleteEdges_adj.mp, in693_cycle_third, Ne.symm

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

    lines 153–162

    uses SimpleGraph.deleteEdges_adj.mp, Sym2.eq_iff, Ne.symm

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

    lines 163–181

    uses Ne.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
  10. 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}.

    lines 182–193

    uses in693_cycle_two_of_three, False.elim

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

    lines 194–209

    uses Ne.symm, Sym2.eq_iff, False.elim

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

    lines 210–224

    uses Finset.card_le_card, Ne.symm

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

    lines 225–234

    uses Finset.card_le_card

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

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