AFTD Auto-Formalizing Theoretical Domains

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]
See it in the graphDiscuss this resultChallenge it