AFTD Auto-Formalizing Theoretical Domains

tournament_directed_cut_eq_of_outdegrees_eq

theoremverifiedformalization

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.

  1. 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.

    line 8

    uses tournament_cut_count_eq_sub

      rw [tournament_cut_count_eq_sub n T₁ hT₁ S, tournament_cut_count_eq_sub n T₂ hT₂ S]
  2. 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.

    line 9

      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

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