tournament_is_strong_king
def
A vertex v in a finite directed graph D is a strong king if for every in-neighbor u of v (that is, every vertex u with an arc from u to v), the number of directed two-paths from v to u is strictly greater than the number of directed two-paths from u to v.
Statement
def tournament_is_strong_king {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (v : V) : Prop
- Defined in
- arXiv:2610.39702, Definition in Section 2.1
- Verified
- 30 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- Used by 2
- 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…
- tournament_max_out_degree_is_strong_kingIn any finite tournament T, every vertex v of maximum out-degree is a strong king.
Read back from the Lean
For a finite type V, a directed graph D on V with decidable adjacency, and a vertex v : V, tournament_is_strong_king D v asserts that for every vertex u : V, if there is a directed edge from u to v (D.Adj u v), then the number of directed two-step paths from u to v is strictly less than the number of directed two-step paths from v to u.
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
/-- Predicate that a vertex is a strong king: for every in-neighbor u, there are strictly more 2-paths from v to u than from u to v. -/ def tournament_is_strong_king {V : Type*} [Fintype V] (D : Digraph V) [DecidableRel D.Adj] (v : V) : Prop := ∀ u, D.Adj u v → digraph_two_path_count D u v < digraph_two_path_count D v u