AFTD Auto-Formalizing Theoretical Domains

is_k_geodetic_bot

theoremverified

The empty graph on any vertex type V is K-geodetic for every natural number K.

Statement

theorem is_k_geodetic_bot {V : Type*} (K : ℕ) :
    is_k_geodetic (⊥ : SimpleGraph V) K
Source
arXiv:2611.05762, Definition 1.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_k_geodeticA 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.
  • 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).

Read back from the Lean

For any type V and any natural number K, the empty graph ⊥ on vertex set V is K-geodetic (that is, between any two distinct vertices, the number of geodesics 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.

The proof, explained

A graph is K-geodetic if between any two distinct vertices there are at most K geodesic walks. In the empty graph, no walk exists between distinct vertices u and v, because a length-zero walk requires u = v and any longer walk requires an edge. Therefore, the set of geodesic walks between u and v is empty, so its cardinality is 0, which is at most K for any natural number K.

  1. Let u and v be distinct vertices; it suffices to show that there are at most K geodesic walks between them in the empty graph.

    By definition, a graph is K-geodetic if for all vertices u ≠ v, the cardinality of the subtype of geodesic walks from u to v is at most K. We introduce distinct vertices u and v with the hypothesis huv : u ≠ v.

    line 4

      intro u v huv
  2. The type of geodesic walks from u to v in the empty graph is empty.

    To show the type is empty, suppose there were a walk p from u to v. Any walk is either a single vertex (nil) or begins with an edge (cons). If p is nil, then u = v, contradicting huv. If p starts with an edge, that edge must connect two vertices in the empty graph ⊥, which is impossible by SimpleGraph.bot_adj. Thus, no such walk exists.

    lines 5–8

    uses SimpleGraph.bot_adj

      have : IsEmpty {p : (⊥ : SimpleGraph V).Walk u v // is_geodesic p} := ⟨fun ⟨p, _⟩ => by
        cases p with
        | nil => exact huv rfl
        | cons h _ => exact (SimpleGraph.bot_adj _ _).mp h⟩
  3. The number of geodesic walks from u to v is at most K.

    Because the type of geodesic walks is empty, its cardinality is 0 by Nat.card_of_isEmpty, and 0 ≤ K holds for any natural number K by Nat.zero_le.

    line 9

    uses Nat.card_of_isEmpty, Nat.zero_le

      simp only [Nat.card_of_isEmpty, Nat.zero_le]
SimpleGraph.bot_adj
In the empty graph ⊥, no two vertices are adjacent (bot.Adj v w ↔ False).
Nat.card_of_isEmpty
The cardinality of an empty type is 0.
Nat.zero_le
For any natural number n, 0 ≤ n.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The empty graph is K-geodetic for all K. -/theorem is_k_geodetic_bot {V : Type*} (K : ℕ) :    is_k_geodetic (⊥ : SimpleGraph V) K := by  intro u v huv  have : IsEmpty {p : (⊥ : SimpleGraph V).Walk u v // is_geodesic p} := ⟨fun ⟨p, _⟩ => by    cases p with    | nil => exact huv rfl    | cons h _ => exact (SimpleGraph.bot_adj _ _).mp h⟩  simp only [Nat.card_of_isEmpty, Nat.zero_le]
See it in the graphDiscuss this resultChallenge it