is_k_geodetic_bot
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.
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.
intro u v huvThe 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.
uses
SimpleGraph.bot_adjhave : 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⟩
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.
uses
Nat.card_of_isEmpty,Nat.zero_lesimp 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]