AFTD Auto-Formalizing Theoretical Domains

oriented_diameter_bound_holds

def

oriented_diameter_bound_holds d k: every finite connected bridgeless simple graph of diameter d (taken on vertex set Fin n, which loses nothing) has a strong orientation of directed diameter at most k. In the paper's notation this says f(d) <= k, where f(d) is the smallest such k.

Statement

def oriented_diameter_bound_holds (d k : ℕ) : Prop
Defined in
arXiv:2610.09648 (An asymptotically tight bound on oriented diameter), Section 1: the function f(d), the smallest integer such that every finite connected bridgeless simple graph of diameter d admits a strong orientation of diameter at most f(d); f(d) <= k iff this predicate holds.
Verified
25 Oct 2026
Axioms
none listed
Built on 1
Used by 2
  • oriented_diameter_bound_holds_monoIf every connected bridgeless graph of diameter d has a strong orientation of diameter at most k, the same holds for every k' >= k (f(d)…
  • oriented_diameter_four_lower_boundf(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most…

Lean source view module on GitHub

def oriented_diameter_bound_holds (d k : ℕ) : Prop :=
  ∀ (n : ℕ) (G : SimpleGraph (Fin n)), G.Connected → (∀ e, ¬ G.IsBridge e) → G.diam = d →
    has_strong_orientation_of_diameter_le G k
See it in the graphDiscuss this resultChallenge it