tournament_directed_cut_eq_of_outdegrees_eq
Let 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 ⊆ Fin n, the number of edges directed from S to its complement in T₁ equals that in T₂.
Statement
open Classical in theorem tournament_directed_cut_eq_of_outdegrees_eq (n : ℕ) (T₁ T₂ : Digraph (Fin n)) (hT₁ : digraph_is_tournament T₁) (hT₂ : digraph_is_tournament T₂) (hdeg : ∀ v : Fin n, digraph_out_count T₁ v = digraph_out_count T₂ v) (S : Finset (Fin n)) : digraph_cut_count T₁ S Sᶜ = digraph_cut_count T₂ S Sᶜ
- Formalizes
- arXiv:2610.40521 Lemma 2: Directed Cut-Query Complexity of Finding a King
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- digraph_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
- 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.
Read back from the Lean
For any natural number n, any two directed graphs T₁ and T₂ on vertex type Fin n, and any vertex subset S : Finset (Fin n): if T₁ and T₂ are tournaments (loopless and having an edge in exactly one direction between any two distinct vertices), and if every vertex v : Fin n has the same out-degree in T₁ as in T₂ (where the out-degree is the number of vertices w with an edge from v to w), then the number of directed edges from S to its complement Sᶜ in T₁ is equal to the number of directed edges from S to Sᶜ in T₂.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
In any tournament, the number of edges directed from a vertex subset S to its complement Sᶜ is determined entirely by the outdegrees of vertices in S: it equals their sum minus the (|S| choose 2) edges directed between pairs inside S. Rewriting both cut sizes using this identity reduces the equality of cut sizes to the equality of the sums of outdegrees. Because T₁ and T₂ have identical outdegrees at every vertex, the two sums coincide.
The directed cut size from S to Sᶜ in each tournament equals the sum of the outdegrees in S minus (|S| choose 2).
By the lemma tournament_cut_count_eq_sub applied to both T₁ and T₂, the number of directed edges from S to Sᶜ in any tournament equals the sum of the outdegrees of the vertices in S minus the (|S| choose 2) edges between pairs of vertices inside S. Rewriting with this lemma for both T₁ and T₂ transforms the goal into showing that these two formulas evaluate to the same value.
uses
tournament_cut_count_eq_subrw [tournament_cut_count_eq_sub n T₁ hT₁ S, tournament_cut_count_eq_sub n T₂ hT₂ S]The two expressions are identical, completing the proof.
By the hypothesis (hdeg) that every vertex v has the same outdegree in T₁ as in T₂, rewriting the outdegree terms for T₁ into those for T₂ makes the left-hand and right-hand sides identical.
simp_rw [hdeg]
tournament_cut_count_eq_sub- In a tournament on n vertices, the number of directed edges from a subset of vertices S to its complement Sᶜ equals the sum of the outdegrees of vertices in S minus (card S choose 2).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Classical in/-- Directed cut sizes in tournaments depend only on vertex outdegrees. -/theorem tournament_directed_cut_eq_of_outdegrees_eq (n : ℕ) (T₁ T₂ : Digraph (Fin n)) (hT₁ : digraph_is_tournament T₁) (hT₂ : digraph_is_tournament T₂) (hdeg : ∀ v : Fin n, digraph_out_count T₁ v = digraph_out_count T₂ v) (S : Finset (Fin n)) : digraph_cut_count T₁ S Sᶜ = digraph_cut_count T₂ S Sᶜ := by rw [tournament_cut_count_eq_sub n T₁ hT₁ S, tournament_cut_count_eq_sub n T₂ hT₂ S] simp_rw [hdeg]