simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees
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
- simple_graph_triangle_degree_le_choosetd_G(v) ≤ C(deg v, 2).
- simple_graph_compl_regular_triangle_distinctIf G is an r-regular triangle-distinct graph on N vertices, its complement is an (N − r − 1)-regular triangle-distinct graph.
- simple_graph_triangle_degreeThe triangle-degree td_G(v): the number of triangles of G containing v, i.e. the number of 2-element subsets {u, w} of the neighbourhood…
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- simple_graph_triangle_degree_complLet G be an r-regular simple graph on N vertices. For every vertex v, td_{Ḡ}(v) = C(N − r − 1, 2) − N r / 2 + r² − td_G(v), where Ḡ is the…
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}.
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.
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_filterintro 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
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.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.nonempty_iff_ne_empty,SimpleGraph.mem_neighborFinsethave 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
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.
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_degreehave 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]
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.
uses
SimpleGraph.mem_neighborFinsethave 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
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.
uses
Finset.mem_filter,Finset.mem_powersetCard,Finset.card_powersetCard,SimpleGraph.card_neighborFinset_eq_degreehave 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
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.
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
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.
uses
Fintype.card_fin,simple_graph_compl_regular_triangle_distincthave 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
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.
uses
simple_graph_triangle_degree_complhave 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)
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.
uses
simple_graph_triangle_degree_le_choose,simple_graph_regular_eight_triangle_distinct_fin_fifteen_degrees_no_fifteen,Finset.mem_Icchave 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
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.
uses
Finset.eq_of_subset_of_card_le,Fintype.card_fin,Finset.card_image_of_injective,Nat.card_Iccapply 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]