tournament_two_path_diff_eq_out_degree_diff
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
- tournament_strong_king_iff_in_neighbor_out_degree_leIn any finite tournament T, a vertex v is a strong king if and only if every in-neighbor u of v (that is, every vertex u with an arc from…
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.
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).
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
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).
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
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.
uses
Finset.disjoint_lefthave 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
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.
uses
Finset.disjoint_lefthave 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
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.
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
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.
uses
Ne.symmhave 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
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.
uses
not_orhave 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⟩
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).
uses
Finset.card_union_of_disjointhave 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]
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.
uses
Finset.card_insert_of_notMem,Finset.card_union_of_disjointhave 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]
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.
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
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.
/-- 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