AFTD Auto-Formalizing Theoretical Domains

tournament_cut_count_eq_sub

lemmaverified

In any tournament T on vertex set Fin n and for any subset S of vertices, the directed cut size from S to its complement Sᶜ equals the sum of the outdegrees of vertices in S minus Nat.choose S.card 2.

Statement

open Classical in
lemma tournament_cut_count_eq_sub (n : ℕ) (T : Digraph (Fin n))
    (hT : digraph_is_tournament T) (S : Finset (Fin n)) :
    digraph_cut_count T S Sᶜ = (∑ v ∈ S, digraph_out_count T v) - Nat.choose S.card 2
Source
arXiv:2610.40521 Lemma 2, Equation (1)
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

Read back from the Lean

For any natural number $n$, any directed graph $T$ on the vertex set $\text{Fin } n$, any hypothesis that $T$ is a tournament (meaning $T$ has no self-loops and for every pair of distinct vertices $x \ne y$, there is an edge from $x$ to $y$ if and only if there is no edge from $y$ to $x$), and any finite subset $S \subseteq \text{Fin } n$: The number of directed edges in $T$ from $S$ to its complement $S^c$ equals the sum over all $v \in S$ of the out-degree of $v$ in $T$, minus $\binom{|S|}{2}$ (in $\mathbb{N}$).

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

Lean source view module on GitHub

open Classical in
/-- Directed cut size c_T(S) equals the sum of outdegrees in S minus (|S| choose 2). -/
lemma tournament_cut_count_eq_sub (n : ℕ) (T : Digraph (Fin n))
    (hT : digraph_is_tournament T) (S : Finset (Fin n)) :
    digraph_cut_count T S Sᶜ = (∑ v ∈ S, digraph_out_count T v) - Nat.choose S.card 2 := by
  have h1 := tournament_cut_add_cut_compl_eq_sum_out_count n T S
  have h2 := tournament_cut_count_self_eq_choose_two n T hT S
  omega
See it in the graphDiscuss this resultChallenge it