AFTD Auto-Formalizing Theoretical Domains

simple_graph_regular_forty_induced_thirty_five_total_dominating

theoremverified

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.

  1. 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.

    lines 6–15

    uses Finset.mem_inter, SimpleGraph.mem_neighborFinset, Finset.mem_erase, Finset.card_le_card, Finset.card_erase_of_mem

      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]
  2. 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.

    lines 16–27

    uses Finset.sum_le_sum, Finset.sum_const

      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
  3. 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.

    lines 28–37

    uses Finset.card_erase_of_mem, Finset.mem_inter, SimpleGraph.mem_neighborFinset, Finset.mem_erase, Finset.eq_of_subset_of_card_le

      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])
  4. 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.

    lines 38–56

    uses Finset.mem_inter, SimpleGraph.mem_neighborFinset, Finset.mem_singleton, Finset.mem_erase, SimpleGraph.is3Clique_triple_iff.mpr, Finset.card_le_card, Finset.card_singleton

      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
  5. 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.

    lines 57–65

    uses Finset.insert_erase, Finset.notMem_erase, Finset.sum_insert, Finset.sum_le_sum, Finset.sum_const

      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
      omega
  6. 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.

    lines 73–88

    uses Finset.card_sdiff, SimpleGraph.card_neighborFinset_eq_degree, Finset.card_inter_add_card_sdiff

      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
  7. 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.

    lines 89–112

    uses Finset.mem_inter, Finset.mem_filter, SimpleGraph.mem_neighborFinset, Finset.card_filter, SimpleGraph.adj_comm, Finset.sum_congr, Finset.sum_comm, Finset.sum_const

      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
  8. 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.

    lines 113–126

    uses SimpleGraph.card_neighborFinset_eq_degree, Finset.card_inter_add_card_sdiff, Finset.sum_congr, Finset.sum_const, Finset.sum_add_distrib

      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
  9. 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.

    lines 127–135

    uses Finset.nonempty_iff_ne_empty, Finset.mem_inter, SimpleGraph.mem_neighborFinset

      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⟩
  10. 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.

    lines 136–168

    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

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
See it in the graphDiscuss this resultChallenge it