AFTD Auto-Formalizing Theoretical Domains

tournament_two_path_diff_eq_out_degree_diff

theoremverifiedformalization

In any finite tournament T, if there is an arc from u to v, then the difference between the number of directed two-paths from v to u and from u to v equals the out-degree of v minus the out-degree of u plus 1: p(v, u) - p(u, v) = d⁺(v) - d⁺(u) + 1.

Statement

theorem tournament_two_path_diff_eq_out_degree_diff {V : Type*} [Fintype V] (T : Digraph V) [DecidableRel T.Adj] (hT : digraph_is_tournament T) {u v : V} (huv : T.Adj u v) : (digraph_two_path_count T v u : ℤ) - (digraph_two_path_count T u v : ℤ) = (digraph_out_degree T v : ℤ) - (digraph_out_degree T u : ℤ) + 1
Formalizes
arXiv:2610.39702 Lemma 2.3 -- Quantum Query Complexity of Tournament Solutions
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • digraph_two_path_countThe number of directed paths of length two from u to v in a finite directed graph D, defined as the number of vertices w such that D has…
  • digraph_out_degreeThe out-degree d⁺(v) of a vertex v in a finite directed graph D is the number of out-neighbors of v, that is, the cardinality of the set…
  • 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

Read back from the Lean

For any finite type $V$, let $T$ be a directed graph on $V$ with decidable adjacency relation $T.\mathrm{Adj}$. Assume $T$ is a tournament (it has no self-loops, and for all distinct $x, y \in V$, exactly one of the directed edges between $x$ and $y$ is present). Let $u, v \in V$ such that there is an edge from $u$ to $v$ ($T.\mathrm{Adj}\ u\ v$). Then the number of two-step paths from $v$ to $u$ minus the number of two-step paths from $u$ to $v$ (as integers) equals the out-degree of $v$ minus the out-degree of $u$, plus $1$.

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

The proof partitions the out-neighborhoods of u and v to express their out-degrees in terms of directed two-paths and common out-neighbors. Given an arc u → v in tournament T, the out-neighborhood of v is the disjoint union of intermediate vertices P on two-paths v → · → u and common out-neighbors C, giving d⁺(v) = p(v, u) + |C|. The out-neighborhood of u decomposes into {v}, intermediate vertices Q on two-paths u → · → v, and C, giving d⁺(u) = p(u, v) + |C| + 1. Subtracting these two cardinality formulas cancels |C| and immediately yields p(v, u) - p(u, v) = d⁺(v) - d⁺(u) + 1.

  1. The vertices u and v are distinct, and there is no directed arc from v to u.

    By definition, a tournament is irreflexive and has exactly one directed arc between any two distinct vertices. Since there is an arc u → v (huv), u ≠ v because otherwise there would be a self-loop u → u. By asymmetry between distinct vertices, u → v implies there is no arc v → u (hvu).

    lines 3–6

      classical
      obtain ⟨hirr, htour⟩ := hT
      have huv_ne : u ≠ v := by rintro rfl; exact hirr u huv
      have hvu : ¬ T.Adj v u := (htour u v huv_ne).mp huv
  2. Define the vertex sets P, Q, and C.

    We define P as the set of intermediate vertices on directed two-paths from v to u (v → w and w → u), Q as the intermediate vertices on directed two-paths from u to v (u → w and w → v), and C as the set of common out-neighbors of u and v (u → w and v → w).

    lines 7–9

      set P : Finset V := Finset.univ.filter (fun w => T.Adj v w ∧ T.Adj w u) with hP
      set Q : Finset V := Finset.univ.filter (fun w => T.Adj u w ∧ T.Adj w v) with hQ
      set C : Finset V := Finset.univ.filter (fun w => T.Adj u w ∧ T.Adj v w) with hC
  3. The sets P and C are disjoint.

    Suppose w ∈ P ∩ C. Then w satisfies both w → u (from w ∈ P) and u → w (from w ∈ C). If w = u, this creates a self-loop u → u, contradicting irreflexivity. If w ≠ u, having both directed arcs between u and w contradicts the tournament property. Hence P and C share no vertices.

    lines 10–18

    uses Finset.disjoint_left

      have hdisjPC : Disjoint P C := by
        rw [hP, hC, Finset.disjoint_left]
        intro w hw hw'
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw hw'
        obtain ⟨-, hwu⟩ := hw
        obtain ⟨huw, -⟩ := hw'
        by_cases h : w = u
        · exact hirr u (h ▸ hwu)
        · exact (htour w u h).mp hwu huw
  4. The sets Q and C are disjoint.

    Suppose w ∈ Q ∩ C. Then w → v (from w ∈ Q) and v → w (from w ∈ C). If w = v, this yields a self-loop v → v, violating irreflexivity. If w ≠ v, having mutual arcs between v and w contradicts the tournament property. Thus Q and C are disjoint.

    lines 19–27

    uses Finset.disjoint_left

      have hdisjQC : Disjoint Q C := by
        rw [hQ, hC, Finset.disjoint_left]
        intro w hw hw'
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw hw'
        obtain ⟨-, hwv⟩ := hw
        obtain ⟨-, hvw⟩ := hw'
        by_cases h : w = v
        · exact hirr v (h ▸ hwv)
        · exact (htour w v h).mp hwv hvw
  5. The out-neighborhood of v is the disjoint union P ∪ C.

    Let w be any out-neighbor of v (v → w). Since there is no arc v → u, w ≠ u. By the tournament property for {u, w}, either w → u (meaning w ∈ P) or u → w (meaning w ∈ C). In reverse, every element of P or C is an out-neighbor of v by definition.

    lines 28–40

      have hA : (Finset.univ.filter (T.Adj v)) = P ∪ C := by
        rw [hP, hC]
        ext w
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union]
        constructor
        · intro hvw
          have hwu : w ≠ u := by rintro rfl; exact hvu hvw
          by_cases h : T.Adj w u
          · exact Or.inl ⟨hvw, h⟩
          · exact Or.inr ⟨(htour u w hwu.symm).mpr h, hvw⟩
        · rintro (⟨hvw, -⟩ | ⟨-, hvw⟩)
          · exact hvw
          · exact hvw
  6. The out-neighborhood of u is the union {v} ∪ (Q ∪ C).

    Let w be an out-neighbor of u (u → w). If w = v, then w is in the singleton {v}. If w ≠ v, the tournament property between v and w dictates that either w → v (so w ∈ Q) or v → w (so w ∈ C). Conversely, v is an out-neighbor because u → v holds by assumption, and vertices in Q and C are out-neighbors of u by definition.

    lines 41–55

    uses Ne.symm

      have hB : (Finset.univ.filter (T.Adj u)) = insert v (Q ∪ C) := by
        rw [hQ, hC]
        ext w
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_insert]
        constructor
        · intro huw
          by_cases hwv : w = v
          · exact Or.inl hwv
          · by_cases h : T.Adj w v
            · exact Or.inr (Or.inl ⟨huw, h⟩)
            · exact Or.inr (Or.inr ⟨huw, (htour v w (Ne.symm hwv)).mpr h⟩)
        · rintro (rfl | ⟨huw, -⟩ | ⟨huw, -⟩)
          · exact huv
          · exact huw
          · exact huw
  7. The vertex v is not in Q ∪ C.

    If v were in Q, then v → v would hold from the second condition defining Q. If v were in C, then v → v would hold from the second condition defining C. Both contradict the irreflexivity of the tournament.

    lines 56–59

    uses not_or

      have hvnot : v ∉ Q ∪ C := by
        rw [hQ, hC]
        simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, not_or]
        exact ⟨fun h => hirr v h.2, fun h => hirr v h.2⟩
  8. The out-degree of v equals p(v, u) + |C|.

    The out-degree d⁺(v) is the size of the out-neighborhood of v, which equals |P ∪ C|. Since P and C are disjoint, this is |P| + |C|. By definition, |P| is the count of directed two-paths p(v, u).

    lines 60–62

    uses Finset.card_union_of_disjoint

      have h1 : digraph_out_degree T v = digraph_two_path_count T v u + C.card := by
        rw [digraph_out_degree, digraph_two_path_count, ← hP]
        rw [hA, Finset.card_union_of_disjoint hdisjPC]
  9. The out-degree of u equals p(u, v) + |C| + 1.

    The out-neighborhood of u is {v} ∪ (Q ∪ C). Since v ∉ Q ∪ C, inserting v adds 1 to the size. Since Q and C are disjoint, |Q ∪ C| = |Q| + |C|. Finally, |Q| is the count of directed two-paths p(u, v), giving d⁺(u) = p(u, v) + |C| + 1.

    lines 63–65

    uses Finset.card_insert_of_notMem, Finset.card_union_of_disjoint

      have h2 : digraph_out_degree T u = digraph_two_path_count T u v + C.card + 1 := by
        rw [digraph_out_degree, digraph_two_path_count, ← hQ]
        rw [hB, Finset.card_insert_of_notMem hvnot, Finset.card_union_of_disjoint hdisjQC]
  10. p(v, u) - p(u, v) = d⁺(v) - d⁺(u) + 1. automation

    Subtracting d⁺(u) = p(u, v) + |C| + 1 from d⁺(v) = p(v, u) + |C| cancels the common term |C| and yields d⁺(v) - d⁺(u) = p(v, u) - p(u, v) - 1. Rearranging this linear equation in ℤ completes the proof.

    line 66

      omega
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities: |s ∪ t| = |s| + |t|.
Finset.card_insert_of_notMem
Inserting an element not already present into a finite set increases its cardinality by 1: |{a} ∪ s| = |s| + 1.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
not_or
The negation of a disjunction is the conjunction of the negations: ¬(p ∨ q) ↔ ¬p ∧ ¬q.

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

/-- In a tournament, if u → v then p(v, u) - p(u, v) = d⁺(v) - d⁺(u) + 1. -/theorem tournament_two_path_diff_eq_out_degree_diff {V : Type*} [Fintype V] (T : Digraph V) [DecidableRel T.Adj] (hT : digraph_is_tournament T) {u v : V} (huv : T.Adj u v) : (digraph_two_path_count T v u : ℤ) - (digraph_two_path_count T u v : ℤ) = (digraph_out_degree T v : ℤ) - (digraph_out_degree T u : ℤ) + 1 := by  classical  obtain ⟨hirr, htour⟩ := hT  have huv_ne : u ≠ v := by rintro rfl; exact hirr u huv  have hvu : ¬ T.Adj v u := (htour u v huv_ne).mp huv  set P : Finset V := Finset.univ.filter (fun w => T.Adj v w ∧ T.Adj w u) with hP  set Q : Finset V := Finset.univ.filter (fun w => T.Adj u w ∧ T.Adj w v) with hQ  set C : Finset V := Finset.univ.filter (fun w => T.Adj u w ∧ T.Adj v w) with hC  have hdisjPC : Disjoint P C := by    rw [hP, hC, Finset.disjoint_left]    intro w hw hw'    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw hw'    obtain ⟨-, hwu⟩ := hw    obtain ⟨huw, -⟩ := hw'    by_cases h : w = u    · exact hirr u (h ▸ hwu)    · exact (htour w u h).mp hwu huw  have hdisjQC : Disjoint Q C := by    rw [hQ, hC, Finset.disjoint_left]    intro w hw hw'    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw hw'    obtain ⟨-, hwv⟩ := hw    obtain ⟨-, hvw⟩ := hw'    by_cases h : w = v    · exact hirr v (h ▸ hwv)    · exact (htour w v h).mp hwv hvw  have hA : (Finset.univ.filter (T.Adj v)) = P ∪ C := by    rw [hP, hC]    ext w    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union]    constructor    · intro hvw      have hwu : w ≠ u := by rintro rfl; exact hvu hvw      by_cases h : T.Adj w u      · exact Or.inl ⟨hvw, h⟩      · exact Or.inr ⟨(htour u w hwu.symm).mpr h, hvw⟩    · rintro (⟨hvw, -⟩ | ⟨-, hvw⟩)      · exact hvw      · exact hvw  have hB : (Finset.univ.filter (T.Adj u)) = insert v (Q ∪ C) := by    rw [hQ, hC]    ext w    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_union, Finset.mem_insert]    constructor    · intro huw      by_cases hwv : w = v      · exact Or.inl hwv      · by_cases h : T.Adj w v        · exact Or.inr (Or.inl ⟨huw, h⟩)        · exact Or.inr (Or.inr ⟨huw, (htour v w (Ne.symm hwv)).mpr h⟩)    · rintro (rfl | ⟨huw, -⟩ | ⟨huw, -⟩)      · exact huv      · exact huw      · exact huw  have hvnot : v ∉ Q ∪ C := by    rw [hQ, hC]    simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and, not_or]    exact ⟨fun h => hirr v h.2, fun h => hirr v h.2⟩  have h1 : digraph_out_degree T v = digraph_two_path_count T v u + C.card := by    rw [digraph_out_degree, digraph_two_path_count, ← hP]    rw [hA, Finset.card_union_of_disjoint hdisjPC]  have h2 : digraph_out_degree T u = digraph_two_path_count T u v + C.card + 1 := by    rw [digraph_out_degree, digraph_two_path_count, ← hQ]    rw [hB, Finset.card_insert_of_notMem hvnot, Finset.card_union_of_disjoint hdisjQC]  omega
See it in the graphDiscuss this resultChallenge it