AFTD Auto-Formalizing Theoretical Domains

simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees

theoremverified

If G is an 8-regular triangle-distinct graph on the 15 vertices {0,…,14}, then the set of its vertex triangle-degrees is exactly {5,6,…,19}: the triangle-degrees are 15 distinct integers, each between 4 and 19, and the value 4 is impossible.

Statement

theorem simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees
    (G : SimpleGraph (Fin 15)) [DecidableRel G.Adj]
    (hreg : G.IsRegularOfDegree 8) (htd : simple_graph_is_triangle_distinct G) :
    Finset.image (simple_graph_triangle_degree G) Finset.univ = Finset.Icc 5 19
Source
step towards exists_nonempty_regular_eight_triangle_distinct
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

To find the triangle-degree set of an 8-regular triangle-distinct graph G on 15 vertices, we analyze its 6-regular complement graph Gᶜ. We first prove a lemma showing that no vertex in a 6-regular triangle-distinct graph can have triangle degree 15; otherwise, its neighborhood would be a 6-clique, forcing any neighbor to also have a 6-clique neighborhood and triangle degree 15, which contradicts injectivity. Applying this lemma along with the complement formula td(G, v) + td(Gᶜ, v) = 19 shows that td(Gᶜ, v) ≤ 14, and therefore each vertex of G has triangle degree in {5, …, 19}. Finally, because the triangle degrees of the 15 vertices are distinct, the image of the triangle-degree map has size 15 and must be the entire 15-element interval {5, …, 19}.

  1. Assuming for contradiction that v has triangle degree 15 in a 6-regular graph H, its neighborhood N(v) forms a clique.

    Assume v has triangle degree 15. Since H is 6-regular, deg(v) = 6, so the total number of unordered pairs of neighbors of v is (6 choose 2) = 15. The triangle degree counts the pairs in N(v) that are adjacent. Because this count equals the total number of pairs in N(v), the filtered set of adjacent pairs must equal the entire set of pairs in N(v). Hence, every pair of distinct neighbors x, y in N(v) is adjacent.

    lines 6–31

    uses Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree, Finset.filter_subset, Finset.eq_of_subset_of_card_le, Finset.mem_powersetCard, Finset.card_pair, Finset.mem_filter

      intro htd_v
      have hdeg_v : H.degree v = 6 := hreg v
      have hclique : ∀ x ∈ H.neighborFinset v, ∀ y ∈ H.neighborFinset v, x ≠ y → H.Adj x y := by
        have hcard : ((H.neighborFinset v).powersetCard 2).card = 15 := by
          rw [Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree, hdeg_v]
          rfl
        have hsub : ((H.neighborFinset v).powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → H.Adj x y) ⊆
            (H.neighborFinset v).powersetCard 2 := Finset.filter_subset _ _
        have heq : ((H.neighborFinset v).powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → H.Adj x y) =
            (H.neighborFinset v).powersetCard 2 := by
          apply Finset.eq_of_subset_of_card_le hsub
          unfold simple_graph_triangle_degree at htd_v
          rw [htd_v, hcard]
        intro x hx y hy hxy
        have hs : {x, y} ∈ (H.neighborFinset v).powersetCard 2 := by
          rw [Finset.mem_powersetCard]
          refine ⟨?_, ?_⟩
          · intro z hz
            simp only [Finset.mem_insert, Finset.mem_singleton] at hz
            rcases hz with rfl | rfl <;> assumption
          · rw [Finset.card_pair hxy]
        have hs_in : {x, y} ∈ ((H.neighborFinset v).powersetCard 2).filter (fun s => ∀ a ∈ s, ∀ b ∈ s, a ≠ b → H.Adj a b) := by
          rw [heq]
          exact hs
        rw [Finset.mem_filter] at hs_in
        apply hs_in.2 x (by simp) y (by simp) hxy
  2. The neighborhood N(v) is nonempty, so we can pick a neighbor u of v with u ≠ v and deg(u) = 6.

    Because deg(v) = 6, N(v) has cardinality 6 and is nonempty. We can therefore choose a neighbor u in N(v). By definition of neighbor, u is adjacent to v, which implies u ≠ v since simple graphs have no self-loops. By 6-regularity, deg(u) = 6.

    lines 33–44

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.nonempty_iff_ne_empty, SimpleGraph.mem_neighborFinset

      have hcard_v : (H.neighborFinset v).card = 6 := by
        rw [SimpleGraph.card_neighborFinset_eq_degree, hdeg_v]
      have hnonempty : (H.neighborFinset v).Nonempty := by
        rw [Finset.nonempty_iff_ne_empty]
        intro h_empty
        rw [h_empty] at hcard_v
        contradiction
      obtain ⟨u, hu⟩ := hnonempty
      have hvu : H.Adj v u := (H.mem_neighborFinset v u).mp hu
      have huv : H.Adj u v := hvu.symm
      have hne_uv : u ≠ v := huv.ne
      have hdeg_u : H.degree u = 6 := hreg u
  3. The neighborhood N(u) is exactly {v} ∪ (N(v) \ {u}).

    We show {v} ∪ (N(v) \ {u}) ⊆ N(u): v is adjacent to u by symmetry, and every other neighbor w in N(v) \ {u} is adjacent to u because N(v) is a clique. Since v ∉ N(v) by irreflexivity of adjacency, the set {v} ∪ (N(v) \ {u}) has size 1 + (6 - 1) = 6. Since deg(u) = 6, N(u) also has size 6, so this inclusion between sets of equal finite size is an equality.

    lines 46–69

    uses SimpleGraph.mem_neighborFinset, Ne.symm, Finset.card_insert_of_notMem, Finset.singleton_subset_iff, Finset.card_sdiff_of_subset, Finset.card_singleton, Finset.eq_of_subset_of_card_le, SimpleGraph.card_neighborFinset_eq_degree

      have hsub_u : insert v (H.neighborFinset v \ {u}) ⊆ H.neighborFinset u := by
        intro w hw
        simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_singleton] at hw
        rcases hw with rfl | ⟨hw_v, hw_ne_u⟩
        · rw [SimpleGraph.mem_neighborFinset]
          exact huv
        · rw [SimpleGraph.mem_neighborFinset]
          apply hclique u hu w hw_v (Ne.symm hw_ne_u)
    
      have hcard_sub : (insert v (H.neighborFinset v \ {u})).card = 6 := by
        have hv_not_in : v ∉ H.neighborFinset v \ {u} := by
          simp only [Finset.mem_sdiff, Finset.mem_singleton, not_and]
          intro hv_in
          have : H.Adj v v := (H.mem_neighborFinset v v).mp hv_in
          exact (H.irrefl this).elim
        rw [Finset.card_insert_of_notMem hv_not_in]
        have hu_in : {u} ⊆ H.neighborFinset v := by
          rw [Finset.singleton_subset_iff]
          exact hu
        rw [Finset.card_sdiff_of_subset hu_in, Finset.card_singleton, hcard_v]
    
      have heq_u : insert v (H.neighborFinset v \ {u}) = H.neighborFinset u := by
        apply Finset.eq_of_subset_of_card_le hsub_u
        rw [hcard_sub, SimpleGraph.card_neighborFinset_eq_degree, hdeg_u]
  4. The neighborhood N(u) is also a clique.

    Let x, y be distinct vertices in N(u) = {v} ∪ (N(v) \ {u}). They cannot both be v. If one is v and the other is in N(v), they are adjacent because elements of N(v) are neighbors of v. If both are in N(v) \ {u}, they are adjacent because N(v) is a clique. Thus any two distinct vertices in N(u) are adjacent.

    lines 71–83

    uses SimpleGraph.mem_neighborFinset

      have hclique_u : ∀ x ∈ H.neighborFinset u, ∀ y ∈ H.neighborFinset u, x ≠ y → H.Adj x y := by
        intro x hx y hy hxy
        rw [← heq_u] at hx hy
        simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_singleton] at hx hy
        rcases hx with rfl | ⟨hx_v, -⟩
        · rcases hy with rfl | ⟨hy_v, -⟩
          · contradiction
          · rw [SimpleGraph.mem_neighborFinset] at hy_v
            exact hy_v
        · rcases hy with rfl | ⟨hy_v, -⟩
          · rw [SimpleGraph.mem_neighborFinset] at hx_v
            exact hx_v.symm
          · exact hclique x hx_v y hy_v hxy
  5. The vertex u also has triangle degree 15.

    Because N(u) is a clique of size 6, every pair of distinct vertices in N(u) is adjacent. Thus the filtered set of adjacent pairs is all of the 2-element subsets of N(u). Its cardinality is (6 choose 2) = 15, so u has triangle degree 15.

    lines 85–96

    uses Finset.mem_filter, Finset.mem_powersetCard, Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree

      have htd_u : simple_graph_triangle_degree H u = 15 := by
        unfold simple_graph_triangle_degree
        have heq_filter : ((H.neighborFinset u).powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → H.Adj x y) =
            (H.neighborFinset u).powersetCard 2 := by
          ext s
          simp only [Finset.mem_filter]
          refine ⟨fun h => h.1, fun hs => ⟨hs, ?_⟩⟩
          intro a ha b hb hab
          rw [Finset.mem_powersetCard] at hs
          exact hclique_u a (hs.1 ha) b (hs.1 hb) hab
        rw [heq_filter, Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree, hdeg_u]
        rfl
  6. Triangle-distinctness of H yields a contradiction, completing the lemma.

    We have simple_graph_triangle_degree H u = 15 = simple_graph_triangle_degree H v. Since H is triangle-distinct (its triangle-degree map is injective), this implies u = v, which contradicts u ≠ v. Thus no vertex in a 6-regular triangle-distinct graph can have triangle degree 15.

    lines 98–101

      have heq_td : simple_graph_triangle_degree H u = simple_graph_triangle_degree H v := by
        rw [htd_u, htd_v]
      have hu_eq_v := htd heq_td
      exact hne_uv hu_eq_v
  7. The complement graph Gᶜ is 6-regular and triangle-distinct on 15 vertices.

    The vertex set Fin 15 has 15 elements. By the complement theorem simple_graph_compl_regular_triangle_distinct, the complement of an 8-regular triangle-distinct graph on 15 vertices is regular of degree 15 - 8 - 1 = 6 and remains triangle-distinct.

    lines 108–111

    uses Fintype.card_fin, simple_graph_compl_regular_triangle_distinct

      have hN : Fintype.card (Fin 15) = 15 := Fintype.card_fin 15
      have hcompl := simple_graph_compl_regular_triangle_distinct G 8 15 hN hreg htd
      have hreg_c : Gᶜ.IsRegularOfDegree 6 := hcompl.1
      have htd_c : simple_graph_is_triangle_distinct Gᶜ := hcompl.2
  8. For every vertex v, the triangle degrees in G and Gᶜ sum to 19.

    By the complement formula simple_graph_triangle_degree_compl, the triangle degree in Gᶜ satisfies simple_graph_triangle_degree Gᶜ v = (15 - 8 - 1).choose 2 - (15 * 8) / 2 + 8^2 - simple_graph_triangle_degree G v. Evaluating (6 choose 2) - 60 + 64 = 15 - 60 + 64 = 19, rearranging shows that simple_graph_triangle_degree G v + simple_graph_triangle_degree Gᶜ v = 19.

    lines 113–124

    uses simple_graph_triangle_degree_compl

      have hsum : ∀ v : Fin 15, simple_graph_triangle_degree G v + simple_graph_triangle_degree Gᶜ v = 19 := by
        intro v
        have h := simple_graph_triangle_degree_compl G 8 15 hN hreg v
        have hc : (15 - 8 - 1).choose 2 = 15 := rfl
        have h2 : ((15 - 8 - 1).choose 2 : ℚ) - (15 * 8 : ℚ) / 2 + (8 : ℚ) ^ 2 = 19 := by
          rw [hc]; norm_num
        have h3 : (simple_graph_triangle_degree Gᶜ v : ℚ) = 19 - simple_graph_triangle_degree G v := by
          calc (simple_graph_triangle_degree Gᶜ v : ℚ)
            _ = ((15 - 8 - 1).choose 2 : ℚ) - (15 * 8 : ℚ) / 2 + (8 : ℚ) ^ 2 -
                simple_graph_triangle_degree G v := h
            _ = 19 - simple_graph_triangle_degree G v := by rw [h2]
        exact_mod_cast (by linarith : (simple_graph_triangle_degree G v : ℚ) + simple_graph_triangle_degree Gᶜ v = 19)
  9. Every vertex of G has its triangle degree in the interval {5, …, 19}.

    For any vertex v, its degree in Gᶜ is 6, so its triangle degree in Gᶜ is at most (6 choose 2) = 15 by simple_graph_triangle_degree_le_choose. By the lemma proved earlier, the triangle degree cannot equal 15, so it is at most 14. Since the triangle degree in Gᶜ is nonnegative and the two triangle degrees sum to 19, the triangle degree in G satisfies 5 ≤ simple_graph_triangle_degree G v ≤ 19.

    lines 126–143

    uses simple_graph_triangle_degree_le_choose, simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees_no_fifteen, Finset.mem_Icc

      have hsubset : Finset.image (simple_graph_triangle_degree G) Finset.univ ⊆ Finset.Icc 5 19 := by
        intro k hk
        simp only [Finset.mem_image, Finset.mem_univ, true_and] at hk
        obtain ⟨v, rfl⟩ := hk
        rw [Finset.mem_Icc]
        have hdeg_c_v : Gᶜ.degree v = 6 := hreg_c v
        have htd_c_le : simple_graph_triangle_degree Gᶜ v ≤ 15 := by
          have := simple_graph_triangle_degree_le_choose Gᶜ v
          rw [hdeg_c_v] at this
          exact this
        have htd_c_ne : simple_graph_triangle_degree Gᶜ v ≠ 15 :=
          simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees_no_fifteen Gᶜ hreg_c htd_c v
        have htd_c_le_14 : simple_graph_triangle_degree Gᶜ v ≤ 14 := by
          omega
        have hsv := hsum v
        constructor
        · omega
        · omega
  10. The set of triangle degrees of G is exactly the interval {5, …, 19}.

    Because G is triangle-distinct, the triangle degree map is injective, so its image on the 15 vertices of Fin 15 has cardinality 15. The interval {5, …, 19} also has cardinality 19 + 1 - 5 = 15. Since the image is a subset of size 15 of an interval of size 15, it must be the entire interval.

    lines 145–148

    uses Finset.eq_of_subset_of_card_le, Fintype.card_fin, Finset.card_image_of_injective, Nat.card_Icc

      apply Finset.eq_of_subset_of_card_le hsubset
      have hcard_univ : (Finset.univ : Finset (Fin 15)).card = 15 := Fintype.card_fin 15
      have hinj : Function.Injective (simple_graph_triangle_degree G) := htd
      rw [Finset.card_image_of_injective Finset.univ hinj, hcard_univ, Nat.card_Icc]
Finset.card_powersetCard
The number of n-element subsets of a finite set s is (card s).choose n.
SimpleGraph.card_neighborFinset_eq_degree
The cardinality of the neighbor finset of a vertex v equals the degree of v.
Finset.filter_subset
Filtering a finset produces a subset of the original finset.
Finset.eq_of_subset_of_card_le
A subset of a finset with at least as many elements as the superset is equal to the superset.
Finset.mem_powersetCard
A finset belongs to the n-element powerset of t if and only if it is a subset of t with cardinality n.
Finset.card_pair
A pair finset {a, b} of two distinct elements has cardinality 2.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the finset and satisfies the predicate.
Finset.nonempty_iff_ne_empty
A finset is nonempty if and only if it is not the empty set.
SimpleGraph.mem_neighborFinset
A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a.
Finset.card_insert_of_notMem
Inserting an element not in s increases the cardinality of s by 1.
Finset.singleton_subset_iff
The singleton {a} is a subset of s if and only if a ∈ s.
Finset.card_sdiff_of_subset
If s ⊆ t, the cardinality of t \ s is card t - card s.
Finset.card_singleton
The singleton finset {a} has cardinality 1.
Fintype.card_fin
The cardinality of Fin n is n.
simple_graph_compl_regular_triangle_distinct
The complement of an r-regular triangle-distinct graph on N vertices is (N - r - 1)-regular and triangle-distinct.
simple_graph_triangle_degree_compl
Expresses the triangle degree in the complement graph in terms of N, the regularity degree r, and the triangle degree in G.
simple_graph_triangle_degree_le_choose
The triangle degree of a vertex v is at most (degree v).choose 2.
simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees_no_fifteen
In a 6-regular triangle-distinct graph, no vertex has triangle degree 15.
Finset.mem_Icc
An element x is in the closed interval [a, b] if and only if a ≤ x ≤ b.
Finset.card_image_of_injective
The image of a finset under an injective map has the same cardinality as the finset.
Nat.card_Icc
The number of natural numbers in [a, b] is b + 1 - 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

lemma simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees_no_fifteen    {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 ≠ 15 := by  intro htd_v  have hdeg_v : H.degree v = 6 := hreg v  have hclique : ∀ x ∈ H.neighborFinset v, ∀ y ∈ H.neighborFinset v, x ≠ y → H.Adj x y := by    have hcard : ((H.neighborFinset v).powersetCard 2).card = 15 := by      rw [Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree, hdeg_v]      rfl    have hsub : ((H.neighborFinset v).powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → H.Adj x y) ⊆        (H.neighborFinset v).powersetCard 2 := Finset.filter_subset _ _    have heq : ((H.neighborFinset v).powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → H.Adj x y) =        (H.neighborFinset v).powersetCard 2 := by      apply Finset.eq_of_subset_of_card_le hsub      unfold simple_graph_triangle_degree at htd_v      rw [htd_v, hcard]    intro x hx y hy hxy    have hs : {x, y} ∈ (H.neighborFinset v).powersetCard 2 := by      rw [Finset.mem_powersetCard]      refine ⟨?_, ?_⟩      · intro z hz        simp only [Finset.mem_insert, Finset.mem_singleton] at hz        rcases hz with rfl | rfl <;> assumption      · rw [Finset.card_pair hxy]    have hs_in : {x, y} ∈ ((H.neighborFinset v).powersetCard 2).filter (fun s => ∀ a ∈ s, ∀ b ∈ s, a ≠ b → H.Adj a b) := by      rw [heq]      exact hs    rw [Finset.mem_filter] at hs_in    apply hs_in.2 x (by simp) y (by simp) hxy  have hcard_v : (H.neighborFinset v).card = 6 := by    rw [SimpleGraph.card_neighborFinset_eq_degree, hdeg_v]  have hnonempty : (H.neighborFinset v).Nonempty := by    rw [Finset.nonempty_iff_ne_empty]    intro h_empty    rw [h_empty] at hcard_v    contradiction  obtain ⟨u, hu⟩ := hnonempty  have hvu : H.Adj v u := (H.mem_neighborFinset v u).mp hu  have huv : H.Adj u v := hvu.symm  have hne_uv : u ≠ v := huv.ne  have hdeg_u : H.degree u = 6 := hreg u  have hsub_u : insert v (H.neighborFinset v \ {u}) ⊆ H.neighborFinset u := by    intro w hw    simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_singleton] at hw    rcases hw with rfl | ⟨hw_v, hw_ne_u⟩    · rw [SimpleGraph.mem_neighborFinset]      exact huv    · rw [SimpleGraph.mem_neighborFinset]      apply hclique u hu w hw_v (Ne.symm hw_ne_u)  have hcard_sub : (insert v (H.neighborFinset v \ {u})).card = 6 := by    have hv_not_in : v ∉ H.neighborFinset v \ {u} := by      simp only [Finset.mem_sdiff, Finset.mem_singleton, not_and]      intro hv_in      have : H.Adj v v := (H.mem_neighborFinset v v).mp hv_in      exact (H.irrefl this).elim    rw [Finset.card_insert_of_notMem hv_not_in]    have hu_in : {u} ⊆ H.neighborFinset v := by      rw [Finset.singleton_subset_iff]      exact hu    rw [Finset.card_sdiff_of_subset hu_in, Finset.card_singleton, hcard_v]  have heq_u : insert v (H.neighborFinset v \ {u}) = H.neighborFinset u := by    apply Finset.eq_of_subset_of_card_le hsub_u    rw [hcard_sub, SimpleGraph.card_neighborFinset_eq_degree, hdeg_u]  have hclique_u : ∀ x ∈ H.neighborFinset u, ∀ y ∈ H.neighborFinset u, x ≠ y → H.Adj x y := by    intro x hx y hy hxy    rw [← heq_u] at hx hy    simp only [Finset.mem_insert, Finset.mem_sdiff, Finset.mem_singleton] at hx hy    rcases hx with rfl | ⟨hx_v, -⟩    · rcases hy with rfl | ⟨hy_v, -⟩      · contradiction      · rw [SimpleGraph.mem_neighborFinset] at hy_v        exact hy_v    · rcases hy with rfl | ⟨hy_v, -⟩      · rw [SimpleGraph.mem_neighborFinset] at hx_v        exact hx_v.symm      · exact hclique x hx_v y hy_v hxy  have htd_u : simple_graph_triangle_degree H u = 15 := by    unfold simple_graph_triangle_degree    have heq_filter : ((H.neighborFinset u).powersetCard 2).filter (fun s => ∀ x ∈ s, ∀ y ∈ s, x ≠ y → H.Adj x y) =        (H.neighborFinset u).powersetCard 2 := by      ext s      simp only [Finset.mem_filter]      refine ⟨fun h => h.1, fun hs => ⟨hs, ?_⟩⟩      intro a ha b hb hab      rw [Finset.mem_powersetCard] at hs      exact hclique_u a (hs.1 ha) b (hs.1 hb) hab    rw [heq_filter, Finset.card_powersetCard, SimpleGraph.card_neighborFinset_eq_degree, hdeg_u]    rfl  have heq_td : simple_graph_triangle_degree H u = simple_graph_triangle_degree H v := by    rw [htd_u, htd_v]  have hu_eq_v := htd heq_td  exact hne_uv hu_eq_v/-- An 8-regular triangle-distinct graph on 15 vertices has triangle-degree set exactly {5,…,19}. -/theorem simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees    (G : SimpleGraph (Fin 15)) [DecidableRel G.Adj]    (hreg : G.IsRegularOfDegree 8) (htd : simple_graph_is_triangle_distinct G) :    Finset.image (simple_graph_triangle_degree G) Finset.univ = Finset.Icc 5 19 := by  have hN : Fintype.card (Fin 15) = 15 := Fintype.card_fin 15  have hcompl := simple_graph_compl_regular_triangle_distinct G 8 15 hN hreg htd  have hreg_c : Gᶜ.IsRegularOfDegree 6 := hcompl.1  have htd_c : simple_graph_is_triangle_distinct Gᶜ := hcompl.2  have hsum : ∀ v : Fin 15, simple_graph_triangle_degree G v + simple_graph_triangle_degree Gᶜ v = 19 := by    intro v    have h := simple_graph_triangle_degree_compl G 8 15 hN hreg v    have hc : (15 - 8 - 1).choose 2 = 15 := rfl    have h2 : ((15 - 8 - 1).choose 2 : ℚ) - (15 * 8 : ℚ) / 2 + (8 : ℚ) ^ 2 = 19 := by      rw [hc]; norm_num    have h3 : (simple_graph_triangle_degree Gᶜ v : ℚ) = 19 - simple_graph_triangle_degree G v := by      calc (simple_graph_triangle_degree Gᶜ v : ℚ)        _ = ((15 - 8 - 1).choose 2 : ℚ) - (15 * 8 : ℚ) / 2 + (8 : ℚ) ^ 2 -            simple_graph_triangle_degree G v := h        _ = 19 - simple_graph_triangle_degree G v := by rw [h2]    exact_mod_cast (by linarith : (simple_graph_triangle_degree G v : ℚ) + simple_graph_triangle_degree Gᶜ v = 19)  have hsubset : Finset.image (simple_graph_triangle_degree G) Finset.univ ⊆ Finset.Icc 5 19 := by    intro k hk    simp only [Finset.mem_image, Finset.mem_univ, true_and] at hk    obtain ⟨v, rfl⟩ := hk    rw [Finset.mem_Icc]    have hdeg_c_v : Gᶜ.degree v = 6 := hreg_c v    have htd_c_le : simple_graph_triangle_degree Gᶜ v ≤ 15 := by      have := simple_graph_triangle_degree_le_choose Gᶜ v      rw [hdeg_c_v] at this      exact this    have htd_c_ne : simple_graph_triangle_degree Gᶜ v ≠ 15 :=      simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees_no_fifteen Gᶜ hreg_c htd_c v    have htd_c_le_14 : simple_graph_triangle_degree Gᶜ v ≤ 14 := by      omega    have hsv := hsum v    constructor    · omega    · omega  apply Finset.eq_of_subset_of_card_le hsubset  have hcard_univ : (Finset.univ : Finset (Fin 15)).card = 15 := Fintype.card_fin 15  have hinj : Function.Injective (simple_graph_triangle_degree G) := htd  rw [Finset.card_image_of_injective Finset.univ hinj, hcard_univ, Nat.card_Icc]
See it in the graphDiscuss this resultChallenge it