complete_twelve_no_modulo_seven_orientation
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
- simple_graph_has_modulo_orientationA simple graph G on a finite vertex set V has a modulo-q orientation if there exists an orientation directing each edge such that for…
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.
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.
classical rintro ⟨R, ⟨hadj, horient⟩, hbal⟩
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$.
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
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.
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
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.
uses
Finset.card_filter,Finset.sum_comm,Finset.sum_congr,Finset.sum_add_distribhave 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
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$.
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_natset 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
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)$.
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_nathave 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]
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`).
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_nathave 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.
- Double-counting arguments (the total sum of outdegrees in $K_{12}$ and the number of internal edges in $S$) are verified formally by summing indicator functions and exchanging summation order using `Finset.sum_comm`, where on paper one simply uses the standard edge counts $\binom{12}{2} = 66$ and $\binom{6}{2} = 15$.
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.
/-- 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