tournament_cut_count_eq_sub
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
- tournament_cut_add_cut_compl_eq_sum_out_countIn any directed graph T on vertex set Fin n and for any subset S of vertices, the number of directed edges within S plus the number of…
- tournament_cut_count_self_eq_choose_twoIn any tournament T on vertex set Fin n and for any subset S of vertices, the number of directed edges with both endpoints in S equals…
- digraph_cut_counte_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- digraph_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 1
- tournament_directed_cut_eq_of_outdegrees_eqLet T₁ and T₂ be tournaments on vertex set Fin n such that every vertex v has the same outdegree in T₁ and T₂. Then for every subset S ⊆…
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