AFTD Auto-Formalizing Theoretical Domains

is_k_geodetic

def

A simple graph G is K-geodetic if for every pair of distinct vertices u and v, the number of geodesics connecting u and v is at most K.

Statement

def is_k_geodetic {V : Type*} (G : SimpleGraph V) (K : ℕ) : Prop
Defined in
arXiv:2611.05762, Definition 1.1
Verified
05 Nov 2026
Axioms
none listed
Built on 1
  • is_geodesicA walk p from u to v in a simple graph G is a geodesic if it is a simple path whose length equals the graph distance dist(u, v).
Used by 1
  • is_k_geodetic_botThe empty graph on any vertex type V is K-geodetic for every natural number K.

Read back from the Lean

For a simple graph G on vertex type V and a natural number K, is_k_geodetic G K asserts that for all pairs of distinct vertices u, v : V (u ≠ v), the number of geodesics from u to v—measured by Nat.card of the subtype of walks p from u to v that are paths (p.IsPath) and have length equal to the graph distance G.dist u v—is at most K.

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

/-- A simple graph G is K-geodetic if every distinct pair of vertices is connected by at most K geodesics. -/
def is_k_geodetic {V : Type*} (G : SimpleGraph V) (K : ℕ) : Prop := ∀ ⦃u v : V⦄, u ≠ v → Nat.card {p : G.Walk u v // is_geodesic p} ≤ K
See it in the graphDiscuss this resultChallenge it