tournament_cut_add_cut_compl_eq_sum_out_count
lemmaverified
In 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 directed edges from S to its complement Sᶜ equals the sum of the outdegrees of the vertices in S.
Statement
open Classical in lemma tournament_cut_add_cut_compl_eq_sum_out_count (n : ℕ) (T : Digraph (Fin n)) (S : Finset (Fin n)) : digraph_cut_count T S S + digraph_cut_count T S Sᶜ = ∑ v ∈ S, digraph_out_count T v
- Source
- arXiv:2610.40521 Lemma 2 proof
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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_out_countThe out-degree of the vertex v of a digraph on Fin n.
- Used by 1
- tournament_cut_count_eq_subIn 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…
Read back from the Lean
For any natural number $n$, any directed graph $T$ on the vertex set $\mathrm{Fin}(n)$, and any finite subset $S \subseteq \mathrm{Fin}(n)$, the number of directed edges in $T$ from $S$ to $S$ plus the number of directed edges in $T$ from $S$ to $S^{\mathrm{c}}$ (the complement of $S$ in $\mathrm{Fin}(n)$) is equal to the sum over all vertices $v \in S$ of the out-degree of $v$ in $T$.
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 /-- Edges originating in a vertex subset S split into edges within S and edges from S to Sᶜ. -/ lemma tournament_cut_add_cut_compl_eq_sum_out_count (n : ℕ) (T : Digraph (Fin n)) (S : Finset (Fin n)) : digraph_cut_count T S S + digraph_cut_count T S Sᶜ = ∑ v ∈ S, digraph_out_count T v := by simp only [digraph_cut_count, digraph_out_count, Finset.card_filter] rw [Finset.sum_product, Finset.sum_product] rw [← Finset.sum_add_distrib] refine Finset.sum_congr rfl (fun v _ => ?_) rw [← Finset.sum_add_sum_compl S]