simple_graph_six_regular_no_triangle_degree_fourteen
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
- simple_graph_is_triangle_distinctA graph is triangle-distinct (K_3-irregular) when its vertex triangle-degrees are pairwise distinct.
- 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…
- Used by 1
- simple_graph_eight_regular_not_card_fifteenNo 8-regular triangle-distinct simple graph exists on 15 vertices.
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.
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.
uses
Finset.powersetCard_succ_insert,Finset.disjoint_left,Finset.mem_filter,Finset.mem_image,Finset.mem_powersetCard,Finset.mem_insert_selfclassical 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))
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.
uses
Finset.filter_eq_self,Finset.mem_image,Finset.mem_powersetCard,Finset.mem_insert,Finset.mem_singleton,Finset.mem_singleton_selfhave 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
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.
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_disjointhave 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]
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.
uses
SimpleGraph.mem_neighborFinsetclassical 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
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.
uses
Finset.card_filter_add_card_filter_not,Finset.card_powersetCardset 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
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.
uses
Finset.card_eq_one.mp,Finset.mem_powersetCard,Finset.mem_filter,Finset.mem_singleton_self,Finset.card_sdiff,Finset.card_pos,Finset.mem_sdiffobtain ⟨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
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.
uses
Finset.mem_filter,Finset.mem_powersetCard,Finset.mem_insert,Finset.mem_singleton,Finset.card_pair,Ne.symmhave 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)))
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.
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_memhave 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]
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.
uses
simple_graph_six_regular_no_triangle_degree_fourteen_ec_insert,Finset.mem_erase,SimpleGraph.mem_neighborFinset,Finset.insert_erase,Finset.notMem_erasehave 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
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.
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}.
- The cardinality of the non-edge set bad is computed by linear arithmetic (omega) combining the binomial coefficient 6 choose 2 = 15 (evaluated by decide) and the 14 known edges.
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.
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)