AFTD Auto-Formalizing Theoretical Domains

has_strong_orientation_of_diameter_le

def

The simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices u, v is joined by a directed walk of length at most k; i.e. G has a strong orientation of directed diameter at most k (oriented diameter of G is at most k).

Statement

def has_strong_orientation_of_diameter_le {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop
Defined in
arXiv:2610.09648 (An asymptotically tight bound on oriented diameter), Section 1: strong orientation and directed diameter; the oriented diameter is the minimum directed diameter over strong orientations.
Verified
25 Oct 2026
Axioms
none listed
Built on 2
  • digraph_reach_withindigraph_reach_within D k u v: there is a directed walk of length at most k from u to v in the digraph D (equivalently, the directed…
  • is_graph_orientationA digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G…
Used by 4

Lean source view module on GitHub

def has_strong_orientation_of_diameter_le {V : Type*} (G : SimpleGraph V) (k : ℕ) : Prop :=
  ∃ D : Digraph V, is_graph_orientation G D ∧ ∀ u v, digraph_reach_within D k u v
See it in the graphDiscuss this resultChallenge it