AFTD Auto-Formalizing Theoretical Domains

tournament_cut_count_self_eq_choose_two

lemmaverified

In 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 Nat.choose S.card 2.

Statement

open Classical in
lemma tournament_cut_count_self_eq_choose_two (n : ℕ) (T : Digraph (Fin n))
    (hT : digraph_is_tournament T) (S : Finset (Fin n)) :
    digraph_cut_count T S S = Nat.choose S.card 2
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_is_tournamentA digraph is a tournament when it has no loops and between any two distinct vertices there is exactly one arc.
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 $\text{Fin } n$, if $T$ is a tournament (meaning it has no self-loops and for every pair of distinct vertices $x \neq y$, exactly one of the directed edges from $x$ to $y$ or from $y$ to $x$ is present), then for any finite set of vertices $S \subseteq \text{Fin } n$, the number of directed edges in $T$ with both endpoints in $S$ (the cut count from $S$ to $S$) is equal to $\binom{|S|}{2}$.

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
/-- In a tournament, the number of directed edges within any vertex subset S is (|S| choose 2). -/
lemma tournament_cut_count_self_eq_choose_two (n : ℕ) (T : Digraph (Fin n))
    (hT : digraph_is_tournament T) (S : Finset (Fin n)) :
    digraph_cut_count T S S = Nat.choose S.card 2 := by
  have h_out : digraph_cut_count T S S = ∑ i ∈ S, ∑ j ∈ S, (if T.Adj i j then 1 else 0) := by
    dsimp [digraph_cut_count]
    rw [Finset.card_filter]
    exact Finset.sum_product' S S (fun x y => if T.Adj x y then 1 else 0)
  have h_pair : ∀ i j : Fin n,
      ((if T.Adj i j then 1 else 0) + (if T.Adj j i then 1 else 0)) = if i = j then 0 else 1 := by
    intro i j
    by_cases hij : i = j
    · subst hij
      simp [hT.1 i]
    · rw [if_neg hij]
      have h_adj := hT.2 i j hij
      by_cases h : T.Adj i j
      · simp [h, (h_adj.1 h)]
      · simp [h, (h_adj.not.1 h)]
  have h_row : ∀ i ∈ S, ∑ j ∈ S, (if i = j then 0 else 1) = S.card - 1 := by
    intro i hi
    have h_add : (∑ j ∈ S, (if i = j then 0 else 1)) + (∑ j ∈ S, (if i = j then 1 else 0)) =
        ∑ j ∈ S, 1 := by
      rw [← Finset.sum_add_distrib]
      congr 1
      ext j
      split_ifs <;> rfl
    have h_one : (∑ j ∈ S, (if i = j then 1 else 0)) = 1 := by
      rw [Finset.sum_ite_eq S i (fun _ => (1 : ℕ))]
      simp [hi]
    have h_tot : (∑ j ∈ S, (1 : ℕ)) = S.card := by
      simp
    omega
  have h_double : 2 * digraph_cut_count T S S = S.card * (S.card - 1) := by
    rw [h_out, two_mul]
    have hcomm : (∑ i ∈ S, ∑ j ∈ S, (if T.Adj i j then 1 else 0)) =
        ∑ i ∈ S, ∑ j ∈ S, (if T.Adj j i then 1 else 0) := by
      rw [Finset.sum_comm]
    nth_rw 2 [hcomm]
    rw [← Finset.sum_add_distrib]
    simp_rw [← Finset.sum_add_distrib]
    simp_rw [h_pair]
    have h_sum_row : (∑ i ∈ S, ∑ j ∈ S, (if i = j then 0 else 1)) = ∑ i ∈ S, (S.card - 1) := by
      apply Finset.sum_congr rfl
      exact h_row
    rw [h_sum_row]
    simp
  rw [Nat.choose_two_right]
  omega
See it in the graphDiscuss this resultChallenge it