AFTD Auto-Formalizing Theoretical Domains

complete_twelve_no_modulo_seven_orientation

theoremverifiedformalization

The complete graph on 12 vertices does not have a modulo-7 orientation.

Statement

theorem complete_twelve_no_modulo_seven_orientation :
    ¬ simple_graph_has_modulo_orientation (SimpleGraph.completeGraph (Fin 12)) 7
Formalizes
arXiv:2610.07034 Prop. 6.2
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

The complete graph on 12 vertices (with vertex set Fin 12) does not have a modulo-7 orientation. That is, it is impossible to orient the edges of the complete graph on 12 vertices such that at every vertex, the out-degree is congruent modulo 7 to the in-degree.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

Suppose for contradiction that the complete graph on 12 vertices has a modulo-7 orientation. Since every vertex has total degree 11, the modulo-7 balance condition implies that its outdegree satisfies $2 \operatorname{outdeg}(v) \equiv 11 \equiv 4 \pmod 7$, forcing every outdegree to be either 2 or 9. Because the sum of all outdegrees in $K_{12}$ is $\binom{12}{2} = 66$, exactly six vertices must have outdegree 2. Double-counting the directed edges in the sub-orientation induced by these six vertices shows that the sum of their internal outdegrees is $\binom{6}{2} = 15$, yet each such vertex has total outdegree 2 in the whole graph, bounding the sum of internal outdegrees by $6 \times 2 = 12$, an impossibility.

  1. Assume for contradiction that $K_{12}$ admits a modulo-7 orientation.

    We introduce the assumed orientation relation $R$, which orients every edge of the complete graph on 12 vertices in exactly one direction (`hadj`, `horient`) such that at each vertex $v$, the outdegree and indegree are congruent modulo 7 (`hbal`). We seek to derive a contradiction.

    lines 4–5

      classical
      rintro ⟨R, ⟨hadj, horient⟩, hbal⟩
  2. For every vertex $v$, the sum of its outdegree and indegree is 11.

    The sum of the outdegree and indegree at $v$ is rewritten as the sum over all vertices $w$ of the indicator that $R(v, w)$ plus the indicator that $R(w, v)$ holds. When $w = v$, both terms are 0 because simple graphs have no self-loops. When $w \neq v$, the edge between $v$ and $w$ in $K_{12}$ is oriented in exactly one direction, so the sum of indicators is 1. Summing 1 over all $w \neq v$ gives $|\mathrm{Fin}(12) \setminus \{v\}| = 11$.

    lines 7–27

    uses Finset.card_filter, Finset.sum_add_distrib, Finset.sum_congr, Finset.filter_ne'

      have hdeg : ∀ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card + (Finset.univ.filter (fun w => R w v)).card = 11 := by
        intro v
        rw [Finset.card_filter, Finset.card_filter, ← Finset.sum_add_distrib]
        have hterm : ∀ w : Fin 12, (if R v w then (1:ℕ) else 0) + (if R w v then 1 else 0) = if w = v then 0 else 1 := by
          intro w
          by_cases hwv : w = v
          · rw [← hwv]
            have hnv : ¬ R w w := by
              intro h; have := hadj w w h; simp at this
            simp [hnv]
          · have hadjvw : (SimpleGraph.completeGraph (Fin 12)).Adj v w := fun h => hwv h.symm
            rcases horient v w hadjvw with ⟨h1, h2⟩ | ⟨h1, h2⟩
            · simp [h1, h2, hwv]
            · simp [h1, h2, hwv]
        rw [Finset.sum_congr rfl (fun w _ => hterm w)]
        have h1 : (∑ w : Fin 12, if w = v then (0:ℕ) else 1) = ∑ w : Fin 12, if w ≠ v then (1:ℕ) else 0 := by
          apply Finset.sum_congr rfl
          intro w _
          by_cases h : w = v <;> simp [h]
        rw [h1, ← Finset.card_filter (fun w : Fin 12 => w ≠ v), Finset.filter_ne']
        simp
  3. Every vertex has outdegree either 2 or 9.

    Since outdegree plus indegree is 11, the indegree is $11 - \operatorname{outdeg}(v)$. The balance condition states that $\operatorname{outdeg}(v) \equiv \operatorname{indeg}(v) \pmod 7$, so $\operatorname{outdeg}(v) \equiv 11 - \operatorname{outdeg}(v) \pmod 7$, which rearranges in $\mathbb{Z}/7\mathbb{Z}$ to $2 \operatorname{outdeg}(v) \equiv 11 \equiv 4 \pmod 7$. Since $0 \le \operatorname{outdeg}(v) \le 11$, linear arithmetic on remainders shows that the only possible integer values for $\operatorname{outdeg}(v)$ are 2 and 9.

    lines 29–50

    uses Nat.cast_sub, eq_sub_iff_add_eq, two_mul, ZMod.natCast_eq_natCast_iff'

      have hval : ∀ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card = 2 ∨ (Finset.univ.filter (fun w => R v w)).card = 9 := by
        intro v
        have hle : (Finset.univ.filter (fun w => R v w)).card ≤ 11 := by have := hdeg v; omega
        have hi : (Finset.univ.filter (fun w => R w v)).card = 11 - (Finset.univ.filter (fun w => R v w)).card := by
          have := hdeg v; omega
        have h2 : (2 * ((Finset.univ.filter (fun w => R v w)).card : ZMod 7) : ZMod 7) = 11 := by
          have h := hbal v
          rw [hi] at h
          have hcast : ((11 - (Finset.univ.filter (fun w => R v w)).card : ℕ) : ZMod 7)
              = (11 : ZMod 7) - ((Finset.univ.filter (fun w => R v w)).card : ZMod 7) := by
            rw [Nat.cast_sub hle]; push_cast; ring
          rw [hcast] at h
          rw [eq_sub_iff_add_eq] at h
          rw [two_mul]
          exact h
        have h2n : ((2 * (Finset.univ.filter (fun w => R v w)).card : ℕ) : ZMod 7) = ((11 : ℕ) : ZMod 7) := by
          push_cast
          exact h2
        have hmod : (2 * (Finset.univ.filter (fun w => R v w)).card) % 7 = 4 := by
          have := (ZMod.natCast_eq_natCast_iff' (2 * (Finset.univ.filter (fun w => R v w)).card) 11 7).mp h2n
          simpa using this
        omega
  4. The total sum of all outdegrees is 66.

    By swapping the order of summation, the sum of all outdegrees equals the sum of all indegrees. Since the sum of outdegree and indegree at each of the 12 vertices is 11, the total degree sum is $12 \times 11 = 132$. Therefore, twice the total outdegree is 132, meaning the sum of all outdegrees is 66.

    lines 52–62

    uses Finset.card_filter, Finset.sum_comm, Finset.sum_congr, Finset.sum_add_distrib

      have hsum : (∑ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card) = 66 := by
        have hsym : (∑ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card)
                  = (∑ v : Fin 12, (Finset.univ.filter (fun w => R w v)).card) := by
          simp only [Finset.card_filter]
          rw [Finset.sum_comm]
        have htot : (∑ v : Fin 12, ((Finset.univ.filter (fun w => R v w)).card + (Finset.univ.filter (fun w => R w v)).card)) = 132 := by
          rw [Finset.sum_congr rfl (fun v _ => hdeg v)]
          simp
        rw [Finset.sum_add_distrib] at htot
        rw [← hsym] at htot
        omega
  5. Exactly 6 vertices have outdegree 2.

    Let $S$ be the set of vertices with outdegree 2, so the remaining $12 - |S|$ vertices have outdegree 9. Decomposing the total outdegree sum into the contributions from $S$ and its complement gives $2|S| + 9(12 - |S|)$. Setting this equal to the total outdegree of 66 yields $108 - 7|S| = 66$, which uniquely solves to $|S| = 6$.

    lines 64–89

    uses Finset.card_le_univ, Finset.sum_congr, Finset.card_filter_add_card_filter_not, Finset.card_univ, Fintype.card_fin, Finset.sum_ite, Finset.sum_const_nat

      set S : Finset (Fin 12) := Finset.univ.filter (fun v => (Finset.univ.filter (fun w => R v w)).card = 2) with hSdef
      have hScard : S.card = 6 := by
        have hSle : S.card ≤ 12 := by
          have := Finset.card_le_univ S
          simpa using this
        have h1 : (∑ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card)
                = ∑ v : Fin 12, (if (Finset.univ.filter (fun w => R v w)).card = 2 then (2:ℕ) else 9) := by
          apply Finset.sum_congr rfl
          intro v _
          rcases hval v with h | h <;> simp [h]
        have hc : (Finset.univ.filter (fun v => ¬ (Finset.univ.filter (fun w => R v w)).card = 2)).card = 12 - S.card := by
          have hthis := Finset.card_filter_add_card_filter_not (s := Finset.univ) (p := fun v : Fin 12 => (Finset.univ.filter (fun w => R v w)).card = 2)
          simp only [Finset.card_univ, Fintype.card_fin] at hthis
          rw [← hSdef] at hthis
          omega
        have h2 : (∑ v : Fin 12, (if (Finset.univ.filter (fun w => R v w)).card = 2 then (2:ℕ) else 9))
                = 2 * S.card + 9 * (12 - S.card) := by
          rw [Finset.sum_ite]
          rw [Finset.sum_const_nat (m := 2) (fun v _ => rfl), Finset.sum_const_nat (m := 9) (fun v _ => rfl)]
          rw [← hSdef]
          rw [hc]
          omega
        have h3 : 2 * S.card + 9 * (12 - S.card) = 66 := by
          rw [← h2, ← h1]; exact hsum
        show S.card = 6
        omega
  6. The sum of internal outdegrees in the sub-orientation induced by $S$ satisfies $2 \sum_{v \in S} \operatorname{outdeg}_S(v) = |S|(|S| - 1) = 30$.

    Between any two distinct vertices in $S$, exactly one directed edge is present. Writing the sum of internal outdegrees as $\sum_{v \in S} \sum_{w \in S} [R(v, w)]$, doubling this sum and interchanging indices allows combining the terms into $\sum_{v \in S} \sum_{w \in S, w \neq v} 1$. For each $v \in S$, the inner sum over $S \setminus \{v\}$ evaluates to $|S| - 1$. Summing this constant over all $v \in S$ gives $|S|(|S| - 1)$.

    lines 91–131

    uses Finset.sum_congr, Finset.card_filter, Finset.sum_comm, two_mul, Finset.sum_add_distrib, Finset.filter_ne, Finset.card_erase_of_mem, Finset.sum_const_nat

      have h2sum : 2 * (∑ v ∈ S, (S.filter (fun w => R v w)).card) = S.card * (S.card - 1) := by
        have hpair : ∀ v w : Fin 12, (if R v w then (1:ℕ) else 0) + (if R w v then (1:ℕ) else 0) = if v = w then 0 else 1 := by
          intro v w
          by_cases h : v = w
          · rw [h]
            have hnv : ¬ R w w := by
              intro hr; have := hadj w w hr; simp at this
            simp [hnv]
          · have hadjvw : (SimpleGraph.completeGraph (Fin 12)).Adj v w := fun hr => h hr
            rcases horient v w hadjvw with ⟨h1, h2⟩ | ⟨h1, h2⟩
            · simp [h1, h2, h]
            · simp [h1, h2, h]
        have hT_eq : (∑ v ∈ S, (S.filter (fun w => R v w)).card) = ∑ v ∈ S, ∑ w ∈ S, (if R v w then (1:ℕ) else 0) := by
          apply Finset.sum_congr rfl
          intro v _
          rw [Finset.card_filter]
        have hsym : (∑ v ∈ S, ∑ w ∈ S, (if R v w then (1:ℕ) else 0)) = (∑ v ∈ S, ∑ w ∈ S, (if R w v then (1:ℕ) else 0)) := by
          rw [Finset.sum_comm]
        have h2T : 2 * (∑ v ∈ S, ∑ w ∈ S, (if R v w then (1:ℕ) else 0))
                  = ∑ v ∈ S, ∑ w ∈ S, ((if R v w then (1:ℕ) else 0) + (if R w v then (1:ℕ) else 0)) := by
          rw [two_mul]
          nth_rewrite 2 [hsym]
          simp only [Finset.sum_add_distrib]
        have hpost : (∑ v ∈ S, ∑ w ∈ S, ((if R v w then (1:ℕ) else 0) + (if R w v then (1:ℕ) else 0)))
                   = ∑ v ∈ S, ∑ w ∈ S, (if v = w then (0:ℕ) else 1) := by
          apply Finset.sum_congr rfl
          intro v _
          apply Finset.sum_congr rfl
          intro w _
          exact hpair v w
        have hinner : ∀ v ∈ S, (∑ w ∈ S, (if v = w then (0:ℕ) else 1)) = S.card - 1 := by
          intro v hv
          have h1 : (∑ w ∈ S, (if v = w then (0:ℕ) else 1)) = ∑ w ∈ S, (if v ≠ w then (1:ℕ) else 0) := by
            apply Finset.sum_congr rfl
            intro w _
            by_cases h : v = w <;> simp [h]
          rw [h1, ← Finset.card_filter (fun w : Fin 12 => v ≠ w), Finset.filter_ne, Finset.card_erase_of_mem hv]
        have hfinal : (∑ v ∈ S, ∑ w ∈ S, (if v = w then (0:ℕ) else 1)) = S.card * (S.card - 1) := by
          rw [Finset.sum_congr rfl (fun v hv => hinner v hv)]
          exact Finset.sum_const_nat (fun v _ => rfl)
        rw [hT_eq, h2T, hpost, hfinal]
  7. A contradiction arises from the upper bound on the internal outdegrees of $S$.

    Each vertex $v \in S$ has an internal outdegree into $S$ bounded above by its total outdegree in $K_{12}$, which is 2 by the definition of $S$. Consequently, the sum of internal outdegrees is at most $\sum_{v \in S} 2 = 2|S| = 12$. However, double-counting established that twice this sum is $|S|(|S|-1) = 6 \times 5 = 30$, so the sum must equal 15. The contradictory inequality $15 \le 12$ is closed by linear arithmetic (`omega`).

    lines 133–146

    uses Finset.sum_le_sum, Finset.card_le_card, Finset.filter_subset_filter, Finset.subset_univ, Finset.mem_filter.mp, Finset.sum_congr, Finset.sum_const_nat

      have hle : (∑ v ∈ S, (S.filter (fun w => R v w)).card) ≤ ∑ v ∈ S, (Finset.univ.filter (fun w => R v w)).card := by
        apply Finset.sum_le_sum
        intro v hv
        apply Finset.card_le_card
        exact Finset.filter_subset_filter _ (Finset.subset_univ _)
      have hout : (∑ v ∈ S, (Finset.univ.filter (fun w => R v w)).card) = S.card * 2 := by
        have h : ∀ v ∈ S, (Finset.univ.filter (fun w => R v w)).card = 2 := by
          intro v hv
          exact (Finset.mem_filter.mp hv).2
        rw [Finset.sum_congr rfl h]
        exact Finset.sum_const_nat (fun v _ => rfl)
      rw [hScard] at h2sum hout
      rw [hout] at hle
      omega
Finset.card_erase_of_mem
Erasing an element from a finite set containing it decreases the cardinality by 1.
Finset.card_filter
The number of elements in a finite set satisfying a predicate equals the sum of the indicator function of that predicate over the set.
Finset.card_filter_add_card_filter_not
The number of elements in a finite set satisfying a predicate plus the number not satisfying it equals the cardinality of the set.
Finset.card_le_card
A subset of a finite set has cardinality at most that of the ambient set.
Finset.card_le_univ
Any subset of a finite type has size at most the cardinality of the type.
Finset.card_univ
The universal finset of a finite type has cardinality equal to the type cardinality.
Finset.filter_ne
Filtering a finite set by the condition $b \neq a$ equals erasing $b$ from the set.
Finset.filter_ne'
Filtering a finite set by the condition $a \neq b$ equals erasing $b$ from the set.
Finset.filter_subset_filter
Filtering two finite sets by the same predicate preserves set inclusion.
Finset.mem_filter.mp
An element belongs to a filtered set only if it belongs to the base set and satisfies the predicate.
Finset.subset_univ
Every finite set of elements of a finite type is a subset of the universal finset.
Finset.sum_add_distrib
The sum of a pointwise sum of two functions over a finite set equals the sum of the first plus the sum of the second.
Finset.sum_comm
The order of summation in a double finite sum can be exchanged.
Finset.sum_congr
Sums over equal finite sets are equal if the summands agree on every element.
Finset.sum_const_nat
Summing a constant natural number $m$ over a finite set $s$ yields $|s| \cdot m$.
Finset.sum_ite
A sum of an if-then-else expression splits into the sum over elements satisfying the condition and the sum over those that do not.
Finset.sum_le_sum
If each summand $f(i)$ is at most $g(i)$ on a finite set, the sum of $f$ is at most the sum of $g$.
Fintype.card_fin
The standard finite type $\mathrm{Fin}(n)$ has cardinality $n$.
Nat.cast_sub
For natural numbers $m \le n$, the cast of $n - m$ into an additive group with one equals the cast of $n$ minus the cast of $m$.
ZMod.natCast_eq_natCast_iff'
Two natural numbers have equal canonical images in $\mathbb{Z}/c\mathbb{Z}$ if and only if they have the same remainder modulo $c$.
eq_sub_iff_add_eq
In an additive group, $a = b - c$ if and only if $a + c = b$.
two_mul
Multiplication by 2 is equivalent to adding an element to itself.

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

/-- The complete graph on 12 vertices has no modulo-7 orientation. -/theorem complete_twelve_no_modulo_seven_orientation :    ¬ simple_graph_has_modulo_orientation (SimpleGraph.completeGraph (Fin 12)) 7 := by  classical  rintro ⟨R, ⟨hadj, horient⟩, hbal⟩  -- Every vertex has outdegree + indegree = 11.  have hdeg : ∀ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card + (Finset.univ.filter (fun w => R w v)).card = 11 := by    intro v    rw [Finset.card_filter, Finset.card_filter, ← Finset.sum_add_distrib]    have hterm : ∀ w : Fin 12, (if R v w then (1:ℕ) else 0) + (if R w v then 1 else 0) = if w = v then 0 else 1 := by      intro w      by_cases hwv : w = v      · rw [← hwv]        have hnv : ¬ R w w := by          intro h; have := hadj w w h; simp at this        simp [hnv]      · have hadjvw : (SimpleGraph.completeGraph (Fin 12)).Adj v w := fun h => hwv h.symm        rcases horient v w hadjvw with ⟨h1, h2⟩ | ⟨h1, h2⟩        · simp [h1, h2, hwv]        · simp [h1, h2, hwv]    rw [Finset.sum_congr rfl (fun w _ => hterm w)]    have h1 : (∑ w : Fin 12, if w = v then (0:ℕ) else 1) = ∑ w : Fin 12, if w ≠ v then (1:ℕ) else 0 := by      apply Finset.sum_congr rfl      intro w _      by_cases h : w = v <;> simp [h]    rw [h1, ← Finset.card_filter (fun w : Fin 12 => w ≠ v), Finset.filter_ne']    simp  -- Every outdegree is 2 or 9.  have hval : ∀ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card = 2 ∨ (Finset.univ.filter (fun w => R v w)).card = 9 := by    intro v    have hle : (Finset.univ.filter (fun w => R v w)).card ≤ 11 := by have := hdeg v; omega    have hi : (Finset.univ.filter (fun w => R w v)).card = 11 - (Finset.univ.filter (fun w => R v w)).card := by      have := hdeg v; omega    have h2 : (2 * ((Finset.univ.filter (fun w => R v w)).card : ZMod 7) : ZMod 7) = 11 := by      have h := hbal v      rw [hi] at h      have hcast : ((11 - (Finset.univ.filter (fun w => R v w)).card : ℕ) : ZMod 7)          = (11 : ZMod 7) - ((Finset.univ.filter (fun w => R v w)).card : ZMod 7) := by        rw [Nat.cast_sub hle]; push_cast; ring      rw [hcast] at h      rw [eq_sub_iff_add_eq] at h      rw [two_mul]      exact h    have h2n : ((2 * (Finset.univ.filter (fun w => R v w)).card : ℕ) : ZMod 7) = ((11 : ℕ) : ZMod 7) := by      push_cast      exact h2    have hmod : (2 * (Finset.univ.filter (fun w => R v w)).card) % 7 = 4 := by      have := (ZMod.natCast_eq_natCast_iff' (2 * (Finset.univ.filter (fun w => R v w)).card) 11 7).mp h2n      simpa using this    omega  -- The sum of all outdegrees is 66.  have hsum : (∑ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card) = 66 := by    have hsym : (∑ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card)              = (∑ v : Fin 12, (Finset.univ.filter (fun w => R w v)).card) := by      simp only [Finset.card_filter]      rw [Finset.sum_comm]    have htot : (∑ v : Fin 12, ((Finset.univ.filter (fun w => R v w)).card + (Finset.univ.filter (fun w => R w v)).card)) = 132 := by      rw [Finset.sum_congr rfl (fun v _ => hdeg v)]      simp    rw [Finset.sum_add_distrib] at htot    rw [← hsym] at htot    omega  -- Six vertices have outdegree 2.  set S : Finset (Fin 12) := Finset.univ.filter (fun v => (Finset.univ.filter (fun w => R v w)).card = 2) with hSdef  have hScard : S.card = 6 := by    have hSle : S.card ≤ 12 := by      have := Finset.card_le_univ S      simpa using this    have h1 : (∑ v : Fin 12, (Finset.univ.filter (fun w => R v w)).card)            = ∑ v : Fin 12, (if (Finset.univ.filter (fun w => R v w)).card = 2 then (2:ℕ) else 9) := by      apply Finset.sum_congr rfl      intro v _      rcases hval v with h | h <;> simp [h]    have hc : (Finset.univ.filter (fun v => ¬ (Finset.univ.filter (fun w => R v w)).card = 2)).card = 12 - S.card := by      have hthis := Finset.card_filter_add_card_filter_not (s := Finset.univ) (p := fun v : Fin 12 => (Finset.univ.filter (fun w => R v w)).card = 2)      simp only [Finset.card_univ, Fintype.card_fin] at hthis      rw [← hSdef] at hthis      omega    have h2 : (∑ v : Fin 12, (if (Finset.univ.filter (fun w => R v w)).card = 2 then (2:ℕ) else 9))            = 2 * S.card + 9 * (12 - S.card) := by      rw [Finset.sum_ite]      rw [Finset.sum_const_nat (m := 2) (fun v _ => rfl), Finset.sum_const_nat (m := 9) (fun v _ => rfl)]      rw [← hSdef]      rw [hc]      omega    have h3 : 2 * S.card + 9 * (12 - S.card) = 66 := by      rw [← h2, ← h1]; exact hsum    show S.card = 6    omega  -- Double counting: internal edges of S.  have h2sum : 2 * (∑ v ∈ S, (S.filter (fun w => R v w)).card) = S.card * (S.card - 1) := by    have hpair : ∀ v w : Fin 12, (if R v w then (1:ℕ) else 0) + (if R w v then (1:ℕ) else 0) = if v = w then 0 else 1 := by      intro v w      by_cases h : v = w      · rw [h]        have hnv : ¬ R w w := by          intro hr; have := hadj w w hr; simp at this        simp [hnv]      · have hadjvw : (SimpleGraph.completeGraph (Fin 12)).Adj v w := fun hr => h hr        rcases horient v w hadjvw with ⟨h1, h2⟩ | ⟨h1, h2⟩        · simp [h1, h2, h]        · simp [h1, h2, h]    have hT_eq : (∑ v ∈ S, (S.filter (fun w => R v w)).card) = ∑ v ∈ S, ∑ w ∈ S, (if R v w then (1:ℕ) else 0) := by      apply Finset.sum_congr rfl      intro v _      rw [Finset.card_filter]    have hsym : (∑ v ∈ S, ∑ w ∈ S, (if R v w then (1:ℕ) else 0)) = (∑ v ∈ S, ∑ w ∈ S, (if R w v then (1:ℕ) else 0)) := by      rw [Finset.sum_comm]    have h2T : 2 * (∑ v ∈ S, ∑ w ∈ S, (if R v w then (1:ℕ) else 0))              = ∑ v ∈ S, ∑ w ∈ S, ((if R v w then (1:ℕ) else 0) + (if R w v then (1:ℕ) else 0)) := by      rw [two_mul]      nth_rewrite 2 [hsym]      simp only [Finset.sum_add_distrib]    have hpost : (∑ v ∈ S, ∑ w ∈ S, ((if R v w then (1:ℕ) else 0) + (if R w v then (1:ℕ) else 0)))               = ∑ v ∈ S, ∑ w ∈ S, (if v = w then (0:ℕ) else 1) := by      apply Finset.sum_congr rfl      intro v _      apply Finset.sum_congr rfl      intro w _      exact hpair v w    have hinner : ∀ v ∈ S, (∑ w ∈ S, (if v = w then (0:ℕ) else 1)) = S.card - 1 := by      intro v hv      have h1 : (∑ w ∈ S, (if v = w then (0:ℕ) else 1)) = ∑ w ∈ S, (if v ≠ w then (1:ℕ) else 0) := by        apply Finset.sum_congr rfl        intro w _        by_cases h : v = w <;> simp [h]      rw [h1, ← Finset.card_filter (fun w : Fin 12 => v ≠ w), Finset.filter_ne, Finset.card_erase_of_mem hv]    have hfinal : (∑ v ∈ S, ∑ w ∈ S, (if v = w then (0:ℕ) else 1)) = S.card * (S.card - 1) := by      rw [Finset.sum_congr rfl (fun v hv => hinner v hv)]      exact Finset.sum_const_nat (fun v _ => rfl)    rw [hT_eq, h2T, hpost, hfinal]  -- Each internal outdegree is at most the total outdegree = 2 on S.  have hle : (∑ v ∈ S, (S.filter (fun w => R v w)).card) ≤ ∑ v ∈ S, (Finset.univ.filter (fun w => R v w)).card := by    apply Finset.sum_le_sum    intro v hv    apply Finset.card_le_card    exact Finset.filter_subset_filter _ (Finset.subset_univ _)  have hout : (∑ v ∈ S, (Finset.univ.filter (fun w => R v w)).card) = S.card * 2 := by    have h : ∀ v ∈ S, (Finset.univ.filter (fun w => R v w)).card = 2 := by      intro v hv      exact (Finset.mem_filter.mp hv).2    rw [Finset.sum_congr rfl h]    exact Finset.sum_const_nat (fun v _ => rfl)  rw [hScard] at h2sum hout  rw [hout] at hle  omega
See it in the graphDiscuss this resultChallenge it