simple_graph_regular_forty_induced_thirty_five_total_dominating
In a triangle-free 9-regular graph on 40 vertices, the complement of an induced 8-regular 35-vertex subgraph is a total dominating five-set.
Statement
theorem simple_graph_regular_forty_induced_thirty_five_total_dominating
(G : SimpleGraph (Fin 40)) [DecidableRel G.Adj]
(htri : G.CliqueFree 3) (hreg : ∀ v, G.degree v = 9)
(S : Finset (Fin 40)) (hcard : S.card = 35)
(hinner : ∀ v ∈ S, ((G.neighborFinset v) ∩ S).card = 8) :
∀ x, ∃ t ∈ (Finset.univ \ S), G.Adj t x- Source
- Structural link between the induced-35 and total-domination branches for OP-926.
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof shows that the complement T = V \\ S of the 35-vertex induced subgraph is a total dominating 5-set by verifying that every vertex in the graph has a neighbor in T. Because G is 9-regular and each vertex in S has 8 neighbors in S, every vertex in S has exactly 1 neighbor in T, dominating S. Double counting the edges between S and T yields 35 cross-edges, which forces the sum of internal degrees in T to be 5 · 9 - 35 = 10. If any vertex x ∈ T had no neighbor in T, the remaining 4 vertices T \\ {x} would inherit all 10 internal degrees; an auxiliary lemma shows this is impossible in any triangle-free graph, as one vertex with 3 neighbors would force the other three to be mutually non-adjacent with degree at most 1, capping the sum at 6.
Every vertex in U has at most 3 neighbors in U.
Because the graph is simple, a vertex u cannot be adjacent to itself, so its neighbors in U are contained in U \\ {u}. Since |U| = 4, |U \\ {u}| = 3, which implies |N(u) ∩ U| ≤ 3.
uses
Finset.mem_inter,SimpleGraph.mem_neighborFinset,Finset.mem_erase,Finset.card_le_card,Finset.card_erase_of_memclassical have hle3 : ∀ u ∈ U, (H.neighborFinset u ∩ U).card ≤ 3 := by intro u hu have hsub : H.neighborFinset u ∩ U ⊆ U.erase u := by intro w hw simp only [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw rw [Finset.mem_erase] exact ⟨(H.ne_of_adj hw.1).symm, hw.2⟩ calc (H.neighborFinset u ∩ U).card ≤ (U.erase u).card := Finset.card_le_card hsub _ = 3 := by rw [Finset.card_erase_of_mem hu, hU]
At least one vertex in U has degree exactly 3 in U.
If no vertex in U had 3 neighbors in U, then since every degree in U is at most 3, all vertices would have at most 2 neighbors in U. The sum of degrees in U would then be at most 4 · 2 = 8, contradicting the assumption that the sum is 10.
uses
Finset.sum_le_sum,Finset.sum_consthave hex : ∃ u ∈ U, (H.neighborFinset u ∩ U).card = 3 := by by_contra hc push Not at hc have hle2 : ∀ u ∈ U, (H.neighborFinset u ∩ U).card ≤ 2 := by intro u hu have := hle3 u hu have := hc u hu omega have hble : ∑ u ∈ U, (H.neighborFinset u ∩ U).card ≤ ∑ u ∈ U, (2:ℕ) := Finset.sum_le_sum hle2 have h2 : ∑ u ∈ U, (2:ℕ) = 8 := by rw [Finset.sum_const, hU]; norm_num rw [hsum, h2] at hble omega
For a vertex u ∈ U with degree 3, its neighbor set in U is exactly A = U \\ {u}.
The neighbor set N(u) ∩ U is a subset of A = U \\ {u}. Since |A| = 4 - 1 = 3 and |N(u) ∩ U| = 3, the subset has the same cardinality as A, so N(u) ∩ U = A.
uses
Finset.card_erase_of_mem,Finset.mem_inter,SimpleGraph.mem_neighborFinset,Finset.mem_erase,Finset.eq_of_subset_of_card_leobtain ⟨u, hu, hdu⟩ := hex set A : Finset α := U.erase u with hAdef have hAcard : A.card = 3 := by rw [hAdef, Finset.card_erase_of_mem hu, hU] have hsubA : H.neighborFinset u ∩ U ⊆ A := by intro w hw simp only [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw rw [hAdef, Finset.mem_erase] exact ⟨(H.ne_of_adj hw.1).symm, hw.2⟩ have hAeq : H.neighborFinset u ∩ U = A := Finset.eq_of_subset_of_card_le hsubA (by rw [hAcard, hdu])
Every vertex in A has at most 1 neighbor in U.
For any a ∈ A, its neighbors in U must lie in {u}. Indeed, if some neighbor w ∈ N(a) ∩ U were distinct from u, then w would also belong to A. But every vertex in A is adjacent to u, so {u, a, w} would be three mutually adjacent vertices, forming a triangle. This contradicts the assumption that H is triangle-free. Hence |N(a) ∩ U| ≤ |{u}| = 1.
uses
Finset.mem_inter,SimpleGraph.mem_neighborFinset,Finset.mem_singleton,Finset.mem_erase,SimpleGraph.is3Clique_triple_iff.mpr,Finset.card_le_card,Finset.card_singletonhave hAa : ∀ a ∈ A, (H.neighborFinset a ∩ U).card ≤ 1 := by intro a haA have hsub1 : H.neighborFinset a ∩ U ⊆ {u} := by intro w hw simp only [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw rw [Finset.mem_singleton] by_contra hwu have hwA : w ∈ A := by rw [hAdef, Finset.mem_erase]; exact ⟨hwu, hw.2⟩ have haN : H.Adj u a := by have h' : a ∈ H.neighborFinset u ∩ U := by rw [hAeq]; exact haA rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at h' exact h'.1 have hwN : H.Adj u w := by have h' : w ∈ H.neighborFinset u ∩ U := by rw [hAeq]; exact hwA rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at h' exact h'.1 exact hcf {u, a, w} (SimpleGraph.is3Clique_triple_iff.mpr ⟨haN, hwN, hw.1⟩) calc (H.neighborFinset a ∩ U).card ≤ ({u} : Finset α).card := Finset.card_le_card hsub1 _ = 1 := Finset.card_singleton u
No 4-vertex set in a triangle-free graph can have an internal degree sum of 10.
Decomposing U into {u} and A, the sum of internal degrees is |N(u) ∩ U| + ∑_{a ∈ A} |N(a) ∩ U|. Since |N(u) ∩ U| = 3 and each of the 3 vertices in A has internal degree at most 1, this sum cannot exceed 3 + 3 · 1 = 6, contradicting the assumption that it equals 10.
uses
Finset.insert_erase,Finset.notMem_erase,Finset.sum_insert,Finset.sum_le_sum,Finset.sum_consthave hUeq : U = insert u A := by rw [hAdef, Finset.insert_erase hu] have hnotmem : u ∉ A := by rw [hAdef]; exact Finset.notMem_erase u U have hsum_dec : ∑ x ∈ U, (H.neighborFinset x ∩ U).card = (H.neighborFinset u ∩ U).card + ∑ x ∈ A, (H.neighborFinset x ∩ U).card := by rw [hUeq, Finset.sum_insert hnotmem] have hAle : ∑ x ∈ A, (H.neighborFinset x ∩ U).card ≤ ∑ x ∈ A, (1:ℕ) := Finset.sum_le_sum hAa have hA1 : ∑ x ∈ A, (1:ℕ) = 3 := by rw [Finset.sum_const, hAcard]; norm_num rw [hsum_dec, hdu] at hsum omega
The complement T = V \\ S has 5 vertices, and every vertex in S has exactly 1 neighbor in T.
With 40 total vertices and |S| = 35, the complement T has size 40 - 35 = 5. By 9-regularity, every vertex v ∈ S has degree 9. Since 8 of its neighbors are in S, its remaining neighbors must lie in T, giving |N(v) ∩ T| = 9 - 8 = 1.
uses
Finset.card_sdiff,SimpleGraph.card_neighborFinset_eq_degree,Finset.card_inter_add_card_sdiffclassical set T : Finset (Fin 40) := Finset.univ \ S with hT have hTmem : ∀ w : Fin 40, w ∈ T ↔ w ∉ S := by intro w; rw [hT]; simp have hTcard : T.card = 5 := by rw [hT, Finset.card_sdiff]; simp [hcard] have hTeq : ∀ v : Fin 40, G.neighborFinset v ∩ T = G.neighborFinset v \ S := by intro v; ext w; rw [hT]; simp have hS1 : ∀ v ∈ S, (G.neighborFinset v ∩ T).card = 1 := by intro v hv have h9 : (G.neighborFinset v).card = 9 := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg v have h8 : (G.neighborFinset v ∩ S).card = 8 := hinner v hv have hsp := Finset.card_inter_add_card_sdiff (G.neighborFinset v) S rw [hTeq] omega
The sum of cross-degrees from T to S is 35.
Double counting the edges between S and T via sums of indicator functions shows that ∑_{v ∈ S} |N(v) ∩ T| = ∑_{t ∈ T} |N(t) ∩ S|. Because each of the 35 vertices in S has |N(v) ∩ T| = 1, the left-hand sum is 35, so the right-hand sum is also 35.
uses
Finset.mem_inter,Finset.mem_filter,SimpleGraph.mem_neighborFinset,Finset.card_filter,SimpleGraph.adj_comm,Finset.sum_congr,Finset.sum_comm,Finset.sum_consthave hcross : (∑ v ∈ S, (G.neighborFinset v ∩ T).card) = ∑ t ∈ T, (G.neighborFinset t ∩ S).card := by have hrow : ∀ (v : Fin 40) (W : Finset (Fin 40)), (G.neighborFinset v ∩ W).card = ∑ w ∈ W, (if G.Adj v w then 1 else 0) := by intro v W have : G.neighborFinset v ∩ W = W.filter (G.Adj v) := by ext w; simp only [Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset]; tauto rw [this, Finset.card_filter] have hcol : ∀ (t : Fin 40) (W : Finset (Fin 40)), (G.neighborFinset t ∩ W).card = ∑ v ∈ W, (if G.Adj v t then 1 else 0) := by intro t W have : G.neighborFinset t ∩ W = W.filter (fun v => G.Adj v t) := by ext w; simp only [Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset] rw [SimpleGraph.adj_comm]; tauto rw [this, Finset.card_filter] rw [Finset.sum_congr rfl (fun v _ => hrow v T), Finset.sum_comm] apply Finset.sum_congr rfl intro t _ rw [hcol t S] have hsumS : (∑ v ∈ S, (G.neighborFinset v ∩ T).card) = 35 := by rw [Finset.sum_congr rfl (fun v hv => hS1 v hv)] rw [Finset.sum_const, hcard]; norm_num have hcross35 : (∑ t ∈ T, (G.neighborFinset t ∩ S).card) = 35 := by rw [← hcross]; exact hsumS
The sum of internal degrees in the induced subgraph on T is 10.
For each t ∈ T, its neighbors partition into S and T, so |N(t) ∩ S| + |N(t) ∩ T| = deg(t) = 9. Summing over all 5 vertices in T gives 5 · 9 = 45. Subtracting the cross-edge sum ∑_{t ∈ T} |N(t) ∩ S| = 35 yields ∑_{t ∈ T} |N(t) ∩ T| = 45 - 35 = 10.
uses
SimpleGraph.card_neighborFinset_eq_degree,Finset.card_inter_add_card_sdiff,Finset.sum_congr,Finset.sum_const,Finset.sum_add_distribhave hsplit : ∀ t : Fin 40, (G.neighborFinset t ∩ S).card + (G.neighborFinset t ∩ T).card = 9 := by intro t have h9 : (G.neighborFinset t).card = 9 := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg t have hsp := Finset.card_inter_add_card_sdiff (G.neighborFinset t) S rw [← hTeq t] at hsp omega have hsumT : (∑ t ∈ T, (G.neighborFinset t ∩ T).card) = 10 := by have h45 : (∑ t ∈ T, ((G.neighborFinset t ∩ S).card + (G.neighborFinset t ∩ T).card)) = 45 := by rw [Finset.sum_congr rfl (fun t _ => hsplit t)] rw [Finset.sum_const, hTcard]; norm_num rw [Finset.sum_add_distrib, hcross35] at h45 omega
Every vertex in S has a neighbor in T.
For any x ∈ S, we have |N(x) ∩ T| = 1, so N(x) ∩ T is nonempty. Choosing any vertex t in this set gives a neighbor of x in T.
uses
Finset.nonempty_iff_ne_empty,Finset.mem_inter,SimpleGraph.mem_neighborFinsetintro x by_cases hx : x ∈ S · have hd1 : (G.neighborFinset x ∩ T).card = 1 := hS1 x hx have hne : (G.neighborFinset x ∩ T).Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h; rw [h] at hd1; simp at hd1 obtain ⟨t, ht⟩ := hne rw [Finset.mem_inter] at ht exact ⟨t, ht.2, ((SimpleGraph.mem_neighborFinset G x t).mp ht.1).symm⟩
Every vertex in T has a neighbor in T, completing the proof that T is a total dominating set.
Suppose for contradiction that some x ∈ T has no neighbor in T, so |N(x) ∩ T| = 0. Then U = T \\ {x} is a 4-vertex set. Since x has no edges to T, the internal neighborhood of each u ∈ U is the same within U as within T. Thus the internal degree sum on U is ∑_{t ∈ T} |N(t) ∩ T| - |N(x) ∩ T| = 10 - 0 = 10. By the auxiliary lemma, no 4-vertex set in a triangle-free graph can have an internal degree sum of 10. This contradiction shows that every x ∈ T must also have a neighbor in T.
uses
Finset.not_nonempty_iff_eq_empty,Finset.mem_inter,SimpleGraph.mem_neighborFinset,Finset.card_empty,Finset.card_erase_of_mem,Finset.mem_erase.mp,Finset.mem_erase,Finset.sum_congr,Finset.sum_erase_add,simple_graph_regular_forty_induced_thirty_five_total_dominating_four_vertex· have hxT : x ∈ T := by rw [hTmem]; exact hx by_contra hcon push Not at hcon have hdx0 : (G.neighborFinset x ∩ T).card = 0 := by have hempty : G.neighborFinset x ∩ T = ∅ := by rw [← Finset.not_nonempty_iff_eq_empty] rintro ⟨w, hw⟩ rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw exact hcon w hw.2 hw.1.symm rw [hempty, Finset.card_empty] have hUcard : (T.erase x).card = 4 := by rw [Finset.card_erase_of_mem hxT, hTcard] have hsumU : (∑ u ∈ T.erase x, (G.neighborFinset u ∩ (T.erase x)).card) = 10 := by have hrew : ∀ u ∈ T.erase x, G.neighborFinset u ∩ (T.erase x) = G.neighborFinset u ∩ T := by intro u hu have hxu : x ∉ G.neighborFinset u := by rw [SimpleGraph.mem_neighborFinset] exact hcon u (Finset.mem_erase.mp hu).2 ext w rw [Finset.mem_inter, Finset.mem_inter] constructor · rintro ⟨hwN, hwU⟩ exact ⟨hwN, (Finset.mem_erase.mp hwU).2⟩ · rintro ⟨hwN, hwT⟩ refine ⟨hwN, ?_⟩ rw [Finset.mem_erase] exact ⟨by rintro rfl; exact hxu hwN, hwT⟩ rw [Finset.sum_congr rfl (fun u hu => by rw [hrew u hu])] have h := Finset.sum_erase_add T (fun t => (G.neighborFinset t ∩ T).card) hxT rw [hdx0] at h omega exact simple_graph_regular_forty_induced_thirty_five_total_dominating_four_vertex G (T.erase x) htri hUcard hsumU
Finset.card_empty- The cardinality of the empty set is 0.
Finset.card_erase_of_mem- Removing an element from a finite set decreases its cardinality by 1.
Finset.card_filter- The cardinality of a filtered subset equals the sum over the set of the indicator function of the predicate.
Finset.card_inter_add_card_sdiff- For any finite sets s and t, the size of their intersection plus the size of their difference equals the size of s.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most that of the other.
Finset.card_sdiff- The cardinality of t \\ s equals the cardinality of t minus the cardinality of s ∩ t.
Finset.card_singleton- A singleton set has cardinality 1.
Finset.eq_of_subset_of_card_le- If a finite set s is a subset of t and |t| ≤ |s|, then s = t.
Finset.insert_erase- Inserting an element a into s \\ {a} recovers s whenever a ∈ s.
Finset.mem_erase- An element belongs to s \\ {b} if and only if it is not equal to b and belongs to s.
Finset.mem_erase.mp- If x belongs to s \\ {a}, then x ≠ a and x ∈ s.
Finset.mem_filter- An element belongs to {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.mem_inter- An element belongs to s₁ ∩ s₂ if and only if it belongs to both s₁ and s₂.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not the empty set.
Finset.notMem_erase- An element a does not belong to s \\ {a}.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is equal to the empty set.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of their individual sums.
Finset.sum_comm- The order of summation in a double sum over finite sets can be exchanged.
Finset.sum_congr- Sums of functions that agree pointwise on equal finite sets are equal.
Finset.sum_const- The sum of a constant c over a finite set s equals |s| · c.
Finset.sum_erase_add- For a ∈ s, the sum over s \\ {a} plus f(a) equals the sum over s.
Finset.sum_insert- Summing over {a} ∪ s with a ∉ s equals f(a) plus the sum over s.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set, then the sum of f is at most the sum of g.
SimpleGraph.adj_comm- Adjacency in a simple graph is symmetric.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the neighbor finset of a vertex equals its degree.
SimpleGraph.is3Clique_triple_iff.mpr- Three mutually adjacent vertices form a 3-clique (a triangle).
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent.
simple_graph_regular_forty_induced_thirty_five_total_dominating_four_vertex- In a triangle-free graph, no 4-vertex subset can have an internal degree sum of 10.
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_forty_induced_thirty_five_total_dominating_four_vertex {α : Type*} [Fintype α] [DecidableEq α] (H : SimpleGraph α) [DecidableRel H.Adj] (U : Finset α) (hcf : H.CliqueFree 3) (hU : U.card = 4) (hsum : ∑ u ∈ U, (H.neighborFinset u ∩ U).card = 10) : False := by classical have hle3 : ∀ u ∈ U, (H.neighborFinset u ∩ U).card ≤ 3 := by intro u hu have hsub : H.neighborFinset u ∩ U ⊆ U.erase u := by intro w hw simp only [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw rw [Finset.mem_erase] exact ⟨(H.ne_of_adj hw.1).symm, hw.2⟩ calc (H.neighborFinset u ∩ U).card ≤ (U.erase u).card := Finset.card_le_card hsub _ = 3 := by rw [Finset.card_erase_of_mem hu, hU] have hex : ∃ u ∈ U, (H.neighborFinset u ∩ U).card = 3 := by by_contra hc push Not at hc have hle2 : ∀ u ∈ U, (H.neighborFinset u ∩ U).card ≤ 2 := by intro u hu have := hle3 u hu have := hc u hu omega have hble : ∑ u ∈ U, (H.neighborFinset u ∩ U).card ≤ ∑ u ∈ U, (2:ℕ) := Finset.sum_le_sum hle2 have h2 : ∑ u ∈ U, (2:ℕ) = 8 := by rw [Finset.sum_const, hU]; norm_num rw [hsum, h2] at hble omega obtain ⟨u, hu, hdu⟩ := hex set A : Finset α := U.erase u with hAdef have hAcard : A.card = 3 := by rw [hAdef, Finset.card_erase_of_mem hu, hU] have hsubA : H.neighborFinset u ∩ U ⊆ A := by intro w hw simp only [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw rw [hAdef, Finset.mem_erase] exact ⟨(H.ne_of_adj hw.1).symm, hw.2⟩ have hAeq : H.neighborFinset u ∩ U = A := Finset.eq_of_subset_of_card_le hsubA (by rw [hAcard, hdu]) have hAa : ∀ a ∈ A, (H.neighborFinset a ∩ U).card ≤ 1 := by intro a haA have hsub1 : H.neighborFinset a ∩ U ⊆ {u} := by intro w hw simp only [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw rw [Finset.mem_singleton] by_contra hwu have hwA : w ∈ A := by rw [hAdef, Finset.mem_erase]; exact ⟨hwu, hw.2⟩ have haN : H.Adj u a := by have h' : a ∈ H.neighborFinset u ∩ U := by rw [hAeq]; exact haA rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at h' exact h'.1 have hwN : H.Adj u w := by have h' : w ∈ H.neighborFinset u ∩ U := by rw [hAeq]; exact hwA rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at h' exact h'.1 exact hcf {u, a, w} (SimpleGraph.is3Clique_triple_iff.mpr ⟨haN, hwN, hw.1⟩) calc (H.neighborFinset a ∩ U).card ≤ ({u} : Finset α).card := Finset.card_le_card hsub1 _ = 1 := Finset.card_singleton u have hUeq : U = insert u A := by rw [hAdef, Finset.insert_erase hu] have hnotmem : u ∉ A := by rw [hAdef]; exact Finset.notMem_erase u U have hsum_dec : ∑ x ∈ U, (H.neighborFinset x ∩ U).card = (H.neighborFinset u ∩ U).card + ∑ x ∈ A, (H.neighborFinset x ∩ U).card := by rw [hUeq, Finset.sum_insert hnotmem] have hAle : ∑ x ∈ A, (H.neighborFinset x ∩ U).card ≤ ∑ x ∈ A, (1:ℕ) := Finset.sum_le_sum hAa have hA1 : ∑ x ∈ A, (1:ℕ) = 3 := by rw [Finset.sum_const, hAcard]; norm_num rw [hsum_dec, hdu] at hsum omegatheorem simple_graph_regular_forty_induced_thirty_five_total_dominating (G : SimpleGraph (Fin 40)) [DecidableRel G.Adj] (htri : G.CliqueFree 3) (hreg : ∀ v, G.degree v = 9) (S : Finset (Fin 40)) (hcard : S.card = 35) (hinner : ∀ v ∈ S, ((G.neighborFinset v) ∩ S).card = 8) : ∀ x, ∃ t ∈ (Finset.univ \ S), G.Adj t x := by classical set T : Finset (Fin 40) := Finset.univ \ S with hT have hTmem : ∀ w : Fin 40, w ∈ T ↔ w ∉ S := by intro w; rw [hT]; simp have hTcard : T.card = 5 := by rw [hT, Finset.card_sdiff]; simp [hcard] have hTeq : ∀ v : Fin 40, G.neighborFinset v ∩ T = G.neighborFinset v \ S := by intro v; ext w; rw [hT]; simp have hS1 : ∀ v ∈ S, (G.neighborFinset v ∩ T).card = 1 := by intro v hv have h9 : (G.neighborFinset v).card = 9 := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg v have h8 : (G.neighborFinset v ∩ S).card = 8 := hinner v hv have hsp := Finset.card_inter_add_card_sdiff (G.neighborFinset v) S rw [hTeq] omega have hcross : (∑ v ∈ S, (G.neighborFinset v ∩ T).card) = ∑ t ∈ T, (G.neighborFinset t ∩ S).card := by have hrow : ∀ (v : Fin 40) (W : Finset (Fin 40)), (G.neighborFinset v ∩ W).card = ∑ w ∈ W, (if G.Adj v w then 1 else 0) := by intro v W have : G.neighborFinset v ∩ W = W.filter (G.Adj v) := by ext w; simp only [Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset]; tauto rw [this, Finset.card_filter] have hcol : ∀ (t : Fin 40) (W : Finset (Fin 40)), (G.neighborFinset t ∩ W).card = ∑ v ∈ W, (if G.Adj v t then 1 else 0) := by intro t W have : G.neighborFinset t ∩ W = W.filter (fun v => G.Adj v t) := by ext w; simp only [Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset] rw [SimpleGraph.adj_comm]; tauto rw [this, Finset.card_filter] rw [Finset.sum_congr rfl (fun v _ => hrow v T), Finset.sum_comm] apply Finset.sum_congr rfl intro t _ rw [hcol t S] have hsumS : (∑ v ∈ S, (G.neighborFinset v ∩ T).card) = 35 := by rw [Finset.sum_congr rfl (fun v hv => hS1 v hv)] rw [Finset.sum_const, hcard]; norm_num have hcross35 : (∑ t ∈ T, (G.neighborFinset t ∩ S).card) = 35 := by rw [← hcross]; exact hsumS have hsplit : ∀ t : Fin 40, (G.neighborFinset t ∩ S).card + (G.neighborFinset t ∩ T).card = 9 := by intro t have h9 : (G.neighborFinset t).card = 9 := by rw [SimpleGraph.card_neighborFinset_eq_degree]; exact hreg t have hsp := Finset.card_inter_add_card_sdiff (G.neighborFinset t) S rw [← hTeq t] at hsp omega have hsumT : (∑ t ∈ T, (G.neighborFinset t ∩ T).card) = 10 := by have h45 : (∑ t ∈ T, ((G.neighborFinset t ∩ S).card + (G.neighborFinset t ∩ T).card)) = 45 := by rw [Finset.sum_congr rfl (fun t _ => hsplit t)] rw [Finset.sum_const, hTcard]; norm_num rw [Finset.sum_add_distrib, hcross35] at h45 omega intro x by_cases hx : x ∈ S · have hd1 : (G.neighborFinset x ∩ T).card = 1 := hS1 x hx have hne : (G.neighborFinset x ∩ T).Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h; rw [h] at hd1; simp at hd1 obtain ⟨t, ht⟩ := hne rw [Finset.mem_inter] at ht exact ⟨t, ht.2, ((SimpleGraph.mem_neighborFinset G x t).mp ht.1).symm⟩ · have hxT : x ∈ T := by rw [hTmem]; exact hx by_contra hcon push Not at hcon have hdx0 : (G.neighborFinset x ∩ T).card = 0 := by have hempty : G.neighborFinset x ∩ T = ∅ := by rw [← Finset.not_nonempty_iff_eq_empty] rintro ⟨w, hw⟩ rw [Finset.mem_inter, SimpleGraph.mem_neighborFinset] at hw exact hcon w hw.2 hw.1.symm rw [hempty, Finset.card_empty] have hUcard : (T.erase x).card = 4 := by rw [Finset.card_erase_of_mem hxT, hTcard] have hsumU : (∑ u ∈ T.erase x, (G.neighborFinset u ∩ (T.erase x)).card) = 10 := by have hrew : ∀ u ∈ T.erase x, G.neighborFinset u ∩ (T.erase x) = G.neighborFinset u ∩ T := by intro u hu have hxu : x ∉ G.neighborFinset u := by rw [SimpleGraph.mem_neighborFinset] exact hcon u (Finset.mem_erase.mp hu).2 ext w rw [Finset.mem_inter, Finset.mem_inter] constructor · rintro ⟨hwN, hwU⟩ exact ⟨hwN, (Finset.mem_erase.mp hwU).2⟩ · rintro ⟨hwN, hwT⟩ refine ⟨hwN, ?_⟩ rw [Finset.mem_erase] exact ⟨by rintro rfl; exact hxu hwN, hwT⟩ rw [Finset.sum_congr rfl (fun u hu => by rw [hrew u hu])] have h := Finset.sum_erase_add T (fun t => (G.neighborFinset t ∩ T).card) hxT rw [hdx0] at h omega exact simple_graph_regular_forty_induced_thirty_five_total_dominating_four_vertex G (T.erase x) htri hUcard hsumU