Geodetic Graph¶
An undirected unweighted graph in which every vertex pair has exactly one shortest path, though longer alternate paths and some cycles may exist.
Core Idea¶
Geodetic graphs generalize the route uniqueness of trees while weakening it to minimum-length routes. Every pair of vertices must have one and only one geodesic, but the graph may contain cycles and longer alternative paths.
Odd cycles and complete graphs show why the class is broader than trees; even cycles fail at opposite vertices. Recognition can run shortest-path searches from each source while detecting whether any vertex receives a second minimum predecessor.
Structural Signature¶
Sig role-phrases:
- Undirected unweighted graph — Fixes the carrier and path-length convention. It is carrier. Counterfactual: Weights or directions define different geodesic notions.
- Vertex pair — Quantifies the property globally over all two vertices. It is query domain. Counterfactual: Testing selected pairs cannot certify the graph.
- Path length — Orders candidate paths by number of edges. It is optimization rule. Counterfactual: Uniqueness of any path is the stronger tree property.
- Shortest path — Supplies at least one minimum route for a connected pair. It is geodesic. Counterfactual: A disconnected graph fails the all-pairs form unless conventions change.
- Uniqueness condition — Forbids two distinct equal-length minima. It is defining invariant. Counterfactual: Multiple longer paths are allowed.
- Recognition search — Counts or detects predecessor alternatives from each source. It is decision method. Counterfactual: One spanning tree cannot prove all-pairs uniqueness.
What It Is Not¶
- It is not limited to trees.
- It does not require only one path of every length.
- It is stronger than weak geodeticity.
- Weighted and directed variants need separate definitions.
- Closest near-miss. A tree has exactly one path of any length between each pair; a geodetic graph may have cycles and only requires the shortest path to be unique.
Scope of Application¶
- Graph theory. Studies metric uniqueness and structure.
- Network routing. Models unique shortest-route selection.
- Graph algorithms. Supports polynomial recognition.
- Extremal combinatorics. Examines diameter, degree, and cycle constraints.
Clarity¶
State simple/multigraph, undirected and unweighted assumptions, connectedness convention, path-length definition, whether every pair is quantified, and the algorithm used to detect equal minima.
Manages Complexity¶
A single global uniqueness invariant permits rich cyclic structure yet can be falsified by one tied pair, linking metric and structural graph properties.
Abstract Reasoning¶
- Fix the graph and distance convention.
- For each source compute minimum distances.
- Track whether any target has two shortest predecessors or paths.
- Produce a tied pair as a counterexample.
- Certify geodeticity only after all pairs pass.
Knowledge Transfer¶
Unique-route intuition transfers to weighted or directed networks only after edge costs, direction, zero cycles, and tie conventions are specified; unweighted theorems need not survive.
Examples¶
Canonical¶
An odd cycle is geodetic because the two directions between any pair have unequal lengths; the shorter direction is unique.
Mapped back: graph → odd cycle; pair → arbitrary; candidate routes → two; minimum → unique.
Applied / In Practice¶
An even cycle has opposite vertices connected by two equal-length semicircles, so it is not geodetic.
Mapped back: graph → even cycle; pair → opposites; shortest paths → two.
Structural Tensions¶
T1 — Local Forbidden Patterns versus Global Uniqueness. Some small induced subgraphs obstruct geodeticity, but avoiding them alone need not characterize every graph.
Diagnostic: Has all-pairs uniqueness actually been tested?
T2 — Cyclic Richness versus Route Uniqueness. Cycles are permitted only when they do not create equal shortest alternatives.
Diagnostic: Which vertex pair witnesses a tie?
Structural–Framed Character¶
Geodetic Graph is structural as global uniqueness of graph geodesics.
Structural Core vs. Domain Accent¶
The core is graph carrier, shortest-path order, all-pairs quantifier, and uniqueness. Graph theory supplies examples, decomposition, forbidden patterns, and recognition algorithms.
Instantiates / Related Primes¶
This entry is a kind of Network.
-
Approved root. No reviewed parent entails this graph-metric property.
-
Related — shortest path, tree, block graph, odd cycle, and weakly geodetic graph. They provide relation, subset/examples, and relaxation.
Relationships to Other Abstractions¶
Current abstraction Geodetic Graph Domain-specific
Parents (1) — more general patterns this builds on
-
Geodetic Graph is a kind of Network Prime
Geodetic Graph is a strict kind of Network: it is a graph network whose stable differentia is a unique shortest path between every vertex pair.Every reviewed Geodetic Graph instance satisfies Network because it is a graph network whose stable differentia is a unique shortest path between every vertex pair. The child adds the domain-specific restrictions stated in its frozen identity. Network is broader and can occur without the restrictions that define Geodetic Graph.
Hierarchy path (1) — routes to 1 parentless root
- Geodetic Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance
Neighborhood in Abstraction Space¶
Geodetic Graph sits in a crowded region of the domain-specific corpus (37th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Graph Power — 0.92
- Prim’s Algorithm — 0.88
- Loop (Graph Theory) — 0.88
- Prism graph — 0.87
- Lindström–Gessel–Viennot Lemma — 0.87
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Tree. Tell: Has one path altogether, a stronger property.
- Weakly geodetic graph. Tell: Only guarantees uniqueness at distance two.
- Distance-regular graph. Tell: Constrains intersection numbers, not unique geodesics.
- Geodesic graph drawing. Tell: Concerns representation rather than this graph class.
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Geodetic_graph (revision 1329559292).
- Preserved source candidate: https://www.graphclasses.org/classes/gc_96.html
- Preserved source candidate: https://books.google.com/books?id=Pf-VAwAAQBAJ&pg=PA104
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.