is_maximal_geodesic
A geodesic p from u to v is maximal if no adjacent vertex at either endpoint extends it to a strictly longer geodesic.
Statement
def is_maximal_geodesic {V : Type*} {G : SimpleGraph V} {u v : V} (p : G.Walk u v) : Prop
- Defined in
- arXiv:2610.36821 Section 1
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 10
- corona_k1_exists_maximal_geodesicFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exist vertices x, y : V ⊕ V and a walk p…
- edge_geodesic_transversal_bound_of_edge_cutLet G be a connected simple graph. Let S be a finite set of edges of G that is an edge cut induced by a vertex subset X (meaning there…
- edge_cut_transversal_theoremLet G be a connected simple graph. Let S be a finite set of edges of G of cardinality k that is an edge cut induced by a vertex subset X…
- is_geodesic_transversalA finite set S of vertices in a simple graph G is a geodesic transversal if every maximal geodesic in G contains at least one vertex of S.
- corona_k1_is_maximal_geodesic_of_isPath_of_distIn the corona product corona_k1 G of a finite graph G, every walk between distinct pendant leaves Sum.inr u and Sum.inr v that is a path…
- corona_k1_exists_edge_geodesic_transversalFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exists a finset S of edges of the corona…
- not_edge_geodesic_transversal_bound_of_edge_disjointThe statement
edge_geodesic_transversal_bound_of_edge_disjointis false: The statement is false as formalized because it omits a… - exists_geodesic_transversal_of_edge_geodesic_transversalFor any finite edge geodesic transversal T in a simple graph G, there exists a finite vertex geodesic transversal S of G such that the…
- edge_geodesic_transversal_number_corona_k1_card_twoFor every finite type V with Fintype.card V = 2 and every connected simple graph G on V, the edge geodesic transversal number of the…
- corona_k1_maximal_geodesic_endpointsFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, if p is a walk between x and y in corona_k1 G…
Read back from the Lean
For a type V, a simple graph G on V, vertices u, v : V, and a walk p from u to v in G, is_maximal_geodesic p is defined as the proposition that:
1. p is a path (p.IsPath) and the length of p equals the graph distance G.dist u v, and
2. for every vertex w : V, if w is adjacent to u in G (G.Adj w u), then the graph distance from w to v is at most p.length (G.dist w v ≤ p.length), and
3. for every vertex w : V, if v is adjacent to w in G (G.Adj v w), then the graph distance from u to w is at most p.length (G.dist u w ≤ p.length).
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 walk is a maximal geodesic if it is a geodesic that cannot be extended at either endpoint. -/ def is_maximal_geodesic {V : Type*} {G : SimpleGraph V} {u v : V} (p : G.Walk u v) : Prop := (p.IsPath ∧ p.length = G.dist u v) ∧ (∀ w, G.Adj w u → G.dist w v ≤ p.length) ∧ (∀ w, G.Adj v w → G.dist u w ≤ p.length)