tournament_sum_out_count
theoremverified
In a tournament T on Fin n, the out-degrees sum to the number of unordered pairs: ∑_i d_i = n(n-1)/2.
Statement
theorem tournament_sum_out_count (n : ℕ) (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) : ∑ i : Fin n, digraph_out_count T i = n * (n - 1) / 2- Source
- step towards tournament_arborescence_hadamard_bound
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- Used by 2
- tournament_near_regular_card_degreesIn any near-regular tournament on 2m vertices with m ≥ 1, exactly m vertices have out-degree m - 1 and exactly m vertices have out-degree m.
- tournament_not_near_regular_exists_arc_degree_gapIn a tournament on 2m vertices with m ≥ 2 that is not near-regular, there are vertices u, v with an arc u → v and out-degree of v at least…
Lean source view module on GitHub
/-- In a tournament the out-degrees sum to `n(n-1)/2`, the number of pairs. -/ theorem tournament_sum_out_count (n : ℕ) (T : Digraph (Fin n)) [DecidableRel T.Adj] (hT : digraph_is_tournament T) : ∑ i : Fin n, digraph_out_count T i = n * (n - 1) / 2 := by have h_out : ∀ i : Fin n, digraph_out_count T i = ∑ j : Fin n, (if T.Adj i j then 1 else 0) := by intro i dsimp [digraph_out_count] exact Finset.card_filter _ Finset.univ have h_pair : ∀ i j : Fin n, ((if T.Adj i j then 1 else 0) + (if T.Adj j i then 1 else 0)) = if i = j then 0 else 1 := by intro i j by_cases hij : i = j · subst hij simp [hT.1 i] · rw [if_neg hij] have h_adj := hT.2 i j hij by_cases h : T.Adj i j · simp [h, (h_adj.1 h)] · simp [h, (h_adj.not.1 h)] have h_row : ∀ i : Fin n, ∑ j : Fin n, (if i = j then 0 else 1) = n - 1 := by intro i have h_add : (∑ j : Fin n, (if i = j then 0 else 1)) + (∑ j : Fin n, (if i = j then 1 else 0)) = ∑ j : Fin n, 1 := by rw [← Finset.sum_add_distrib] congr 1 ext j split_ifs <;> rfl have h_one : (∑ j : Fin n, (if i = j then 1 else 0)) = 1 := by exact Fintype.sum_ite_eq i (fun _ => 1) have h_tot : (∑ j : Fin n, (1 : ℕ)) = n := by simp omega have h_double : 2 * (∑ i : Fin n, digraph_out_count T i) = n * (n - 1) := by simp_rw [h_out] rw [two_mul] have hcomm : (∑ i : Fin n, ∑ j : Fin n, (if T.Adj i j then 1 else 0)) = ∑ i : Fin n, ∑ j : Fin n, (if T.Adj j i then 1 else 0) := by rw [Finset.sum_comm] nth_rw 2 [hcomm] rw [← Finset.sum_add_distrib] simp_rw [← Finset.sum_add_distrib] simp_rw [h_pair] simp_rw [h_row] simp omega