AFTD Auto-Formalizing Theoretical Domains

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

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