Geodesic Geometry on Graphs

We investigate a graph theoretic analog of geodesic geometry. In a graph $G=(V,E)$ we consider a system of paths $P=\{P_{u,v}| u,v\in V\}$ where $P_{u,v}$ connects vertices $u$ and $v$. This system is consistent in that if vertices $y,z$ are in $P_{u,v}$, then the sub-path of $P_{u,v}$ between them coincides with $P_{y,z}$. A map $w:E\to(0,\infty)$ is said to induce $P$ if for every $u,v\in V$ the path $P_{u,v}$ is $w$-geodesic. We say that $G$ is metrizable if every consistent path system is induced by some such $w$. As we show, metrizable graphs are very rare, whereas there exist infinitely many 2-connected metrizable graphs.