AFTD Auto-Formalizing Theoretical Domains

simple_graph_six_regular_no_triangle_degree_fourteen

theoremverified

In any 6-regular graph, no vertex has triangle-degree 14 if the graph is triangle-distinct.

Statement

theorem simple_graph_six_regular_no_triangle_degree_fourteen {V : Type*} [Fintype V] [DecidableEq V]
    (H : SimpleGraph V) [DecidableRel H.Adj]
    (hreg : H.IsRegularOfDegree 6) (htd : simple_graph_is_triangle_distinct H) (v : V) :
    simple_graph_triangle_degree H v ≠ 14
Source
step towards regular_eight_triangle_distinct_witness
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

We assume for contradiction that some vertex v in a 6-regular graph H has triangle-degree 14. Its neighborhood A = N(v) has 6 vertices and therefore 15 pairs, so exactly one pair s0 is a non-edge. Removing s0 leaves 6 - 2 = 4 vertices; any vertex c ∈ A \ s0 is adjacent to all other vertices in A and to v, making its neighborhood N(c) = {v} ∪ (A \ {c}). Since both v and c are adjacent to all vertices of A \ {c}, the induced edge counts on N(c) and N(v) are identical, giving c triangle-degree 14 as well. By triangle-distinctness, c = v, which contradicts c ∈ N(v) and the fact that simple graphs have no self-loops.

  1. The 2-element subsets of {x} ∪ s partition into the 2-element subsets of s and the pairs {x, y} for y ∈ s.

    We set p to be the predicate that two vertices in a pair are adjacent. We split the 2-element subsets of {x} ∪ s into the 2-element subsets of s and singletons from s with x adjoined, using powersetCard_succ_insert. Since x ∉ s, these two sub-collections are disjoint.

    lines 10–21

    uses Finset.powersetCard_succ_insert, Finset.disjoint_left, Finset.mem_filter, Finset.mem_image, Finset.mem_powersetCard, Finset.mem_insert_self

      classical
      set p : Finset V → Prop := fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → G.Adj a b with hp
      have hsplit : (insert x s).powersetCard 2
          = (s.powersetCard 2) ∪ ((s.powersetCard 1).image (insert x)) := by
        have h := Finset.powersetCard_succ_insert (x := x) (s := s) hx 1
        simpa using h
      have hdisj : Disjoint ((s.powersetCard 2).filter p) (((s.powersetCard 1).image (insert x)).filter p) := by
        rw [Finset.disjoint_left]
        intro t ht1 ht2
        simp only [Finset.mem_filter, Finset.mem_image, Finset.mem_powersetCard] at ht1 ht2
        obtain ⟨⟨u, hu, rfl⟩, -⟩ := ht2
        exact hx (ht1.1.1 (Finset.mem_insert_self x u))
  2. Every pair {x, y} with y ∈ s forms an edge in G.

    Because x is assumed to be adjacent to every vertex in s, filtering the pairs {x, y} by the adjacency predicate p retains every such pair.

    lines 22–37

    uses Finset.filter_eq_self, Finset.mem_image, Finset.mem_powersetCard, Finset.mem_insert, Finset.mem_singleton, Finset.mem_singleton_self

      have hBfilter : ((s.powersetCard 1).image (insert x)).filter p = (s.powersetCard 1).image (insert x) := by
        rw [Finset.filter_eq_self]
        intro t ht
        simp only [Finset.mem_image, Finset.mem_powersetCard] at ht
        obtain ⟨u, ⟨hus, hu1⟩, rfl⟩ := ht
        obtain ⟨y, hyu⟩ := Finset.card_eq_one.mp hu1
        rw [hyu] at hus ⊢
        intro a ha b hb hab
        rw [Finset.mem_insert, Finset.mem_singleton] at ha hb
        rcases ha with ha | ha
        · rcases hb with hb | hb
          · exact absurd (ha.trans hb.symm) hab
          · rw [ha, hb]; exact hadj y (hus (Finset.mem_singleton_self y))
        · rcases hb with hb | hb
          · rw [ha, hb]; exact (hadj y (hus (Finset.mem_singleton_self y))).symm
          · exact absurd (ha.trans hb.symm) hab
  3. Adding a dominating vertex x to s increases the induced edge count by |s|.

    Because x ∉ s, inserting x is injective on the 1-element subsets of s, so there are exactly |s| such pairs. Combining the disjoint decomposition with the edge count on s gives the recurrence.

    lines 38–47

    uses Finset.mem_coe, Finset.mem_powersetCard, congrArg, Finset.erase_insert, Finset.card_image_of_injOn, Finset.card_powersetCard, Nat.choose_one_right, Finset.filter_union, Finset.card_union_of_disjoint

      have hinj : Set.InjOn (insert x) (↑(s.powersetCard 1) : Set (Finset V)) := by
        intro u hu v hv huv
        simp only [Finset.mem_coe, Finset.mem_powersetCard] at hu hv
        have hxu : x ∉ u := fun h => hx (hu.1 h)
        have hxv : x ∉ v := fun h => hx (hv.1 h)
        have hh := congrArg (fun w => w.erase x) huv
        simpa only [Finset.erase_insert hxu, Finset.erase_insert hxv] using hh
      have hBcard : (((s.powersetCard 1).image (insert x))).card = s.card := by
        rw [Finset.card_image_of_injOn hinj, Finset.card_powersetCard, Nat.choose_one_right]
      rw [hsplit, Finset.filter_union, Finset.card_union_of_disjoint hdisj, hBfilter, hBcard]
  4. Assume for contradiction that vertex v has triangle-degree 14, and establish that its neighborhood A has 6 vertices and 14 induced edges, with v ∉ A.

    We assume for contradiction that the triangle-degree of v is 14. We let A = N(v) be the neighborhood of v. Since simple graphs have no self-loops, v ∉ A. Because H is 6-regular, |A| = 6. By definition, the triangle-degree is the number of edges induced by A, which is 14.

    lines 61–68

    uses SimpleGraph.mem_neighborFinset

      classical
      intro h14
      set A := H.neighborFinset v with hA
      have hvA : v ∉ A := by
        rw [hA, SimpleGraph.mem_neighborFinset]; exact H.irrefl
      have hAcard : A.card = 6 := by
        rw [hA, H.card_neighborFinset_eq_degree, hreg v]
      have htdv : simple_graph_six_regular_no_triangle_degree_fourteen_ec H A = 14 := h14
  5. There is exactly 1 non-edge pair among the vertices of A. automation

    The total number of pairs of vertices in A is 6 choose 2 = 15. Since 14 of these pairs are edges, the complement set of non-edge pairs, bad, has cardinality 15 - 14 = 1.

    lines 69–78

    uses Finset.card_filter_add_card_filter_not, Finset.card_powersetCard

      set bad := (A.powersetCard 2).filter (fun t => ¬ (∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b)) with hbad_def
      have hbadcard : bad.card = 1 := by
        have htot : ((A.powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b)).card
            + bad.card = (A.powersetCard 2).card := by
          simpa [hbad_def] using (Finset.card_filter_add_card_filter_not (s := A.powersetCard 2)
            (p := fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b))
        have h1 : ((A.powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b)).card = 14 := htdv
        have h2 : (A.powersetCard 2).card = 15 := by
          rw [Finset.card_powersetCard, hAcard]; decide
        omega
  6. Let s0 be the unique non-edge pair in A; then A \ s0 has size 4, so we can pick a vertex c ∈ A \ s0.

    Since bad has size 1, let s0 be its unique element, which is a 2-element subset of A. Removing s0 from A leaves 6 - 2 = 4 vertices. Since 4 > 0, the difference is nonempty, and we pick a vertex c ∈ A \ s0.

    lines 79–89

    uses Finset.card_eq_one.mp, Finset.mem_powersetCard, Finset.mem_filter, Finset.mem_singleton_self, Finset.card_sdiff, Finset.card_pos, Finset.mem_sdiff

      obtain ⟨s0, hs0⟩ := Finset.card_eq_one.mp hbadcard
      have hs0mem : s0 ∈ A.powersetCard 2 := by
        have h : s0 ∈ bad := by rw [hs0]; exact Finset.mem_singleton_self s0
        exact (Finset.mem_filter.mp h).1
      have hs0sub : s0 ⊆ A := (Finset.mem_powersetCard.mp hs0mem).1
      have hs0card : s0.card = 2 := (Finset.mem_powersetCard.mp hs0mem).2
      have hsdiff : (A \ s0).card = 4 := by
        rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hs0sub, hAcard, hs0card]
      have hne : (A \ s0).Nonempty := by rw [← Finset.card_pos, hsdiff]; norm_num
      obtain ⟨c, hc⟩ := hne
      rw [Finset.mem_sdiff] at hc
  7. The vertex c is adjacent to every other vertex in A.

    If there were some y ∈ A \ {c} not adjacent to c, the pair {c, y} would be a non-edge in A, meaning {c, y} ∈ bad. But bad = {s0}, so {c, y} = s0, implying c ∈ s0, which contradicts c ∈ A \ s0.

    lines 90–108

    uses Finset.mem_filter, Finset.mem_powersetCard, Finset.mem_insert, Finset.mem_singleton, Finset.card_pair, Ne.symm

      have hcgood : ∀ y ∈ A, y ≠ c → H.Adj c y := by
        intro y hyA hyne
        by_contra hnc
        have hpb : ({c, y} : Finset V) ∈ bad := by
          rw [hbad_def, Finset.mem_filter]
          refine ⟨?_, ?_⟩
          · rw [Finset.mem_powersetCard]
            refine ⟨?_, ?_⟩
            · intro z hz
              rw [Finset.mem_insert, Finset.mem_singleton] at hz
              rcases hz with hzc | hzy
              · rw [hzc]; exact hc.1
              · rw [hzy]; exact hyA
            · exact Finset.card_pair (Ne.symm hyne)
          · intro hcl
            exact hnc (hcl c (by simp) y (by simp) (Ne.symm hyne))
        have hceq : ({c, y} : Finset V) = s0 := by
          rw [hs0] at hpb; rwa [Finset.mem_singleton] at hpb
        exact hc.2 (hceq ▸ (by simp : c ∈ ({c, y} : Finset V)))
  8. The neighborhood of c is precisely {v} ∪ (A \ {c}).

    Because c ∈ A = N(v), c is adjacent to v. By the previous step, c is also adjacent to all 5 vertices in A \ {c}. Thus {v} ∪ (A \ {c}) ⊆ N(c). Since v ∉ A, this set has size 1 + 5 = 6. Since H is 6-regular, |N(c)| = 6, so equality holds.

    lines 109–125

    uses SimpleGraph.mem_neighborFinset, Finset.mem_erase, Finset.eq_of_subset_of_card_le, Finset.mem_insert, Finset.card_insert_of_notMem, Finset.card_erase_of_mem

      have hvc : H.Adj v c := by
        have hmem : c ∈ H.neighborFinset v := by rw [← hA]; exact hc.1
        rwa [SimpleGraph.mem_neighborFinset] at hmem
      have hvAerase : v ∉ A.erase c := by
        rw [Finset.mem_erase]; intro h; exact hvA h.2
      have hNc : H.neighborFinset c = insert v (A.erase c) := by
        symm
        refine Finset.eq_of_subset_of_card_le ?_ ?_
        · intro y hy
          rw [Finset.mem_insert] at hy
          rcases hy with rfl | hy
          · rw [SimpleGraph.mem_neighborFinset]; exact hvc.symm
          · rw [Finset.mem_erase] at hy
            rw [SimpleGraph.mem_neighborFinset]
            exact hcgood y hy.2 hy.1
        · rw [H.card_neighborFinset_eq_degree, hreg c, Finset.card_insert_of_notMem hvAerase,
            Finset.card_erase_of_mem hc.1, hAcard]
  9. The induced edge counts on N(c) and A are equal.

    Both v and c are adjacent to all vertices of A \ {c}. Applying the edge count insertion lemma to {v} ∪ (A \ {c}) and to {c} ∪ (A \ {c}) = A shows that each has edge count equal to that of A \ {c} plus |A \ {c}|. Therefore, both sets induce the same number of edges.

    lines 126–142

    uses simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert, Finset.mem_erase, SimpleGraph.mem_neighborFinset, Finset.insert_erase, Finset.notMem_erase

      have step1 : simple_graph_six_regular_no_triangle_degree_fourteen_ec H (insert v (A.erase c))
          = simple_graph_six_regular_no_triangle_degree_fourteen_ec H (A.erase c) + (A.erase c).card := by
        apply simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert
        · exact hvAerase
        · intro y hy
          rw [Finset.mem_erase] at hy
          have hya : y ∈ H.neighborFinset v := by rw [← hA]; exact hy.2
          rwa [SimpleGraph.mem_neighborFinset] at hya
      have step2 : simple_graph_six_regular_no_triangle_degree_fourteen_ec H A
          = simple_graph_six_regular_no_triangle_degree_fourteen_ec H (A.erase c) + (A.erase c).card := by
        conv_lhs => rw [← Finset.insert_erase hc.1]
        apply simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert
        · exact Finset.notMem_erase c A
        · intro y hy
          rw [Finset.mem_erase] at hy
          exact hcgood y hy.2 hy.1
      have hcd14 : simple_graph_triangle_degree H c = 14 := by
  10. The triangle-degree of c is 14, which implies c = v by triangle-distinctness, contradicting v ∉ A.

    Since N(c) has 14 induced edges, the triangle-degree of c is 14, matching that of v. Because H is triangle-distinct, the triangle-degree map is injective, forcing c = v. But c ∈ A while v ∉ A, giving a contradiction.

    lines 143–150

        have hbridge : simple_graph_triangle_degree H c
            = simple_graph_six_regular_no_triangle_degree_fourteen_ec H (H.neighborFinset c) := rfl
        rw [hbridge, hNc, step1, ← step2]
        exact htdv
      have heq : simple_graph_triangle_degree H c = simple_graph_triangle_degree H v := by
        rw [hcd14, h14]
      have hcv : c = v := htd heq
      exact hvA (hcv ▸ hc.1)
Finset.powersetCard_succ_insert
The (n+1)-element subsets of s ∪ {x} (with x ∉ s) are the (n+1)-element subsets of s union the n-element subsets of s each with x inserted.
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_filter
An element belongs to the filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_image
An element belongs to the image of a finset under a function if and only if it is the image of some element in the finset.
Finset.mem_powersetCard
A finset belongs to the powerset of cardinality n of t if and only if it is a subset of t of cardinality n.
Finset.mem_insert_self
An element a is always a member of {a} ∪ s.
Finset.filter_eq_self
Filtering a finset by a predicate yields the entire finset if and only if every element in the finset satisfies the predicate.
Finset.mem_insert
An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Finset.mem_singleton_self
An element a belongs to {a}.
Finset.mem_coe
An element belongs to a finset coerced to a set if and only if it belongs to the finset.
congrArg
Equal arguments yield equal function values.
Finset.erase_insert
Erasing a from {a} ∪ s returns s when a ∉ s.
Finset.card_image_of_injOn
The image of a finset under an injective function has the same cardinality as the finset.
Finset.card_powersetCard
The number of n-element subsets of a finset s is |s| choose n.
Nat.choose_one_right
For any natural number n, n choose 1 = n.
Finset.filter_union
Filtering a union of two finsets by a predicate is the union of the filtered finsets.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
Finset.card_filter_add_card_filter_not
The number of elements in a finset satisfying p plus the number not satisfying p equals the total cardinality.
Finset.card_eq_one.mp
A finset has cardinality 1 if and only if it is a singleton {a}.
Finset.card_sdiff
The cardinality of t \ s is |t| - |s ∩ t|.
Finset.card_pos
A finset has strictly positive cardinality if and only if it is nonempty.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and not to t.
Finset.card_pair
If a ≠ b, then the cardinality of {a, b} is 2.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_erase
An element belongs to s with b erased if and only if it is not b and belongs to s.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Finset.card_insert_of_notMem
If a ∉ s, then |{a} ∪ s| = |s| + 1.
Finset.card_erase_of_mem
If a ∈ s, then |s \ {a}| = |s| - 1.
simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert
If x ∉ s is adjacent to all vertices in s, the induced edge count of {x} ∪ s equals that of s plus |s|.
Finset.insert_erase
If a ∈ s, inserting a into s \ {a} recovers s.
Finset.notMem_erase
An element a does not belong to s \ {a}.

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

abbrev simple_graph_six_regular_no_triangle_degree_fourteen_ec {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (S : Finset V) : ℕ :=  ((S.powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → G.Adj a b)).cardlemma simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert_raw {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x : V) (s : Finset V)    (hx : x ∉ s) (hadj : ∀ y ∈ s, G.Adj x y) :    (((insert x s).powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → G.Adj a b)).card    = (((s.powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → G.Adj a b)).card) + s.card := by  classical  set p : Finset V → Prop := fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → G.Adj a b with hp  have hsplit : (insert x s).powersetCard 2      = (s.powersetCard 2) ∪ ((s.powersetCard 1).image (insert x)) := by    have h := Finset.powersetCard_succ_insert (x := x) (s := s) hx 1    simpa using h  have hdisj : Disjoint ((s.powersetCard 2).filter p) (((s.powersetCard 1).image (insert x)).filter p) := by    rw [Finset.disjoint_left]    intro t ht1 ht2    simp only [Finset.mem_filter, Finset.mem_image, Finset.mem_powersetCard] at ht1 ht2    obtain ⟨⟨u, hu, rfl⟩, -⟩ := ht2    exact hx (ht1.1.1 (Finset.mem_insert_self x u))  have hBfilter : ((s.powersetCard 1).image (insert x)).filter p = (s.powersetCard 1).image (insert x) := by    rw [Finset.filter_eq_self]    intro t ht    simp only [Finset.mem_image, Finset.mem_powersetCard] at ht    obtain ⟨u, ⟨hus, hu1⟩, rfl⟩ := ht    obtain ⟨y, hyu⟩ := Finset.card_eq_one.mp hu1    rw [hyu] at hus ⊢    intro a ha b hb hab    rw [Finset.mem_insert, Finset.mem_singleton] at ha hb    rcases ha with ha | ha    · rcases hb with hb | hb      · exact absurd (ha.trans hb.symm) hab      · rw [ha, hb]; exact hadj y (hus (Finset.mem_singleton_self y))    · rcases hb with hb | hb      · rw [ha, hb]; exact (hadj y (hus (Finset.mem_singleton_self y))).symm      · exact absurd (ha.trans hb.symm) hab  have hinj : Set.InjOn (insert x) (↑(s.powersetCard 1) : Set (Finset V)) := by    intro u hu v hv huv    simp only [Finset.mem_coe, Finset.mem_powersetCard] at hu hv    have hxu : x ∉ u := fun h => hx (hu.1 h)    have hxv : x ∉ v := fun h => hx (hv.1 h)    have hh := congrArg (fun w => w.erase x) huv    simpa only [Finset.erase_insert hxu, Finset.erase_insert hxv] using hh  have hBcard : (((s.powersetCard 1).image (insert x))).card = s.card := by    rw [Finset.card_image_of_injOn hinj, Finset.card_powersetCard, Nat.choose_one_right]  rw [hsplit, Finset.filter_union, Finset.card_union_of_disjoint hdisj, hBfilter, hBcard]lemma simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (x : V) (s : Finset V)    (hx : x ∉ s) (hadj : ∀ y ∈ s, G.Adj x y) :    simple_graph_six_regular_no_triangle_degree_fourteen_ec G (insert x s)      = simple_graph_six_regular_no_triangle_degree_fourteen_ec G s + s.card :=  simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert_raw G x s hx hadj/-- In any 6-regular graph, no vertex has triangle-degree 14 if the graph is triangle-distinct: a neighborhood with 14 edges misses exactly one edge, leaving at least 4 neighbors with full neighborhood in N(v) and thus identical triangle-degree 14. -/theorem simple_graph_six_regular_no_triangle_degree_fourteen {V : Type*} [Fintype V] [DecidableEq V]    (H : SimpleGraph V) [DecidableRel H.Adj]    (hreg : H.IsRegularOfDegree 6) (htd : simple_graph_is_triangle_distinct H) (v : V) :    simple_graph_triangle_degree H v ≠ 14 := by  classical  intro h14  set A := H.neighborFinset v with hA  have hvA : v ∉ A := by    rw [hA, SimpleGraph.mem_neighborFinset]; exact H.irrefl  have hAcard : A.card = 6 := by    rw [hA, H.card_neighborFinset_eq_degree, hreg v]  have htdv : simple_graph_six_regular_no_triangle_degree_fourteen_ec H A = 14 := h14  set bad := (A.powersetCard 2).filter (fun t => ¬ (∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b)) with hbad_def  have hbadcard : bad.card = 1 := by    have htot : ((A.powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b)).card        + bad.card = (A.powersetCard 2).card := by      simpa [hbad_def] using (Finset.card_filter_add_card_filter_not (s := A.powersetCard 2)        (p := fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b))    have h1 : ((A.powersetCard 2).filter (fun t => ∀ a ∈ t, ∀ b ∈ t, a ≠ b → H.Adj a b)).card = 14 := htdv    have h2 : (A.powersetCard 2).card = 15 := by      rw [Finset.card_powersetCard, hAcard]; decide    omega  obtain ⟨s0, hs0⟩ := Finset.card_eq_one.mp hbadcard  have hs0mem : s0 ∈ A.powersetCard 2 := by    have h : s0 ∈ bad := by rw [hs0]; exact Finset.mem_singleton_self s0    exact (Finset.mem_filter.mp h).1  have hs0sub : s0 ⊆ A := (Finset.mem_powersetCard.mp hs0mem).1  have hs0card : s0.card = 2 := (Finset.mem_powersetCard.mp hs0mem).2  have hsdiff : (A \ s0).card = 4 := by    rw [Finset.card_sdiff, Finset.inter_eq_left.mpr hs0sub, hAcard, hs0card]  have hne : (A \ s0).Nonempty := by rw [← Finset.card_pos, hsdiff]; norm_num  obtain ⟨c, hc⟩ := hne  rw [Finset.mem_sdiff] at hc  have hcgood : ∀ y ∈ A, y ≠ c → H.Adj c y := by    intro y hyA hyne    by_contra hnc    have hpb : ({c, y} : Finset V) ∈ bad := by      rw [hbad_def, Finset.mem_filter]      refine ⟨?_, ?_⟩      · rw [Finset.mem_powersetCard]        refine ⟨?_, ?_⟩        · intro z hz          rw [Finset.mem_insert, Finset.mem_singleton] at hz          rcases hz with hzc | hzy          · rw [hzc]; exact hc.1          · rw [hzy]; exact hyA        · exact Finset.card_pair (Ne.symm hyne)      · intro hcl        exact hnc (hcl c (by simp) y (by simp) (Ne.symm hyne))    have hceq : ({c, y} : Finset V) = s0 := by      rw [hs0] at hpb; rwa [Finset.mem_singleton] at hpb    exact hc.2 (hceq ▸ (by simp : c ∈ ({c, y} : Finset V)))  have hvc : H.Adj v c := by    have hmem : c ∈ H.neighborFinset v := by rw [← hA]; exact hc.1    rwa [SimpleGraph.mem_neighborFinset] at hmem  have hvAerase : v ∉ A.erase c := by    rw [Finset.mem_erase]; intro h; exact hvA h.2  have hNc : H.neighborFinset c = insert v (A.erase c) := by    symm    refine Finset.eq_of_subset_of_card_le ?_ ?_    · intro y hy      rw [Finset.mem_insert] at hy      rcases hy with rfl | hy      · rw [SimpleGraph.mem_neighborFinset]; exact hvc.symm      · rw [Finset.mem_erase] at hy        rw [SimpleGraph.mem_neighborFinset]        exact hcgood y hy.2 hy.1    · rw [H.card_neighborFinset_eq_degree, hreg c, Finset.card_insert_of_notMem hvAerase,        Finset.card_erase_of_mem hc.1, hAcard]  have step1 : simple_graph_six_regular_no_triangle_degree_fourteen_ec H (insert v (A.erase c))      = simple_graph_six_regular_no_triangle_degree_fourteen_ec H (A.erase c) + (A.erase c).card := by    apply simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert    · exact hvAerase    · intro y hy      rw [Finset.mem_erase] at hy      have hya : y ∈ H.neighborFinset v := by rw [← hA]; exact hy.2      rwa [SimpleGraph.mem_neighborFinset] at hya  have step2 : simple_graph_six_regular_no_triangle_degree_fourteen_ec H A      = simple_graph_six_regular_no_triangle_degree_fourteen_ec H (A.erase c) + (A.erase c).card := by    conv_lhs => rw [← Finset.insert_erase hc.1]    apply simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert    · exact Finset.notMem_erase c A    · intro y hy      rw [Finset.mem_erase] at hy      exact hcgood y hy.2 hy.1  have hcd14 : simple_graph_triangle_degree H c = 14 := by    have hbridge : simple_graph_triangle_degree H c        = simple_graph_six_regular_no_triangle_degree_fourteen_ec H (H.neighborFinset c) := rfl    rw [hbridge, hNc, step1, ← step2]    exact htdv  have heq : simple_graph_triangle_degree H c = simple_graph_triangle_degree H v := by    rw [hcd14, h14]  have hcv : c = v := htd heq  exact hvA (hcv ▸ hc.1)
See it in the graphDiscuss this resultChallenge it