# Geodesics in polyhedral graphs

Let $e = \lbrace u,v\rbrace$, $e' = \lbrace v,u'\rbrace$ be edges of an undirected graph $G$ and $ee'$ be the path from $u$ through $v$ to $u'$. The following defintions make sense for every graph and thus are purely combinatorial:

Definition 1: $ee'$ is a pre-geodesic when it is the unique shortest path between $u$ and $u'$

Definition 2: A pre-geodesic $ee'$ is a geodesic when there is no other edge $f$ through $v$ such that $ef$ or $e'f$ is a pre-geodesic.

The first condition is motivated by the fact that geodesics in differential geometry are locally shortest paths and as such locally unique. It prevents the graph

from having geodesics.

The second condition reflects the fact, that geodesics usually do not “split”. It prevents the graph

from having geodesics.

But now, let's restrict to polyhedral graphs. I wonder if it's true for polyhedral graphs that only a small number of patterns of geodesics going through a given vertex $v$ are possible:

• Which patterns?

• How to prove this?

Have a look at this gallery of vertices $v$ (grey, drawn with all their neighbours) with degree at most 6 and at most three geodesics (red, blue, green) passing through them (all the other vertices may or must have further neighbours):

• Is this gallery essentially complete?

• If so: how to prove it?

Otherwise:

• Is there a polyhedral graph with a vertex of degree 7 with a geodesic passing through it?

• Is there a polyhedral graph with a vertex with four geodesics passing through it?

-
Am I interpreting this correctly? Every pre-geodesic, and therefore every geodesic, is exactly two edges long...? In your square example, label three consecutive vertices $u,v,u'$. So $(u,v,u')$ is a pre-geodesic. You claim it is not a geodesic. But surely there is no other edge $f$ incident to $v$, so it seems $(u,v,u')$ is a geodesic according to your definition. – Joseph O'Rourke Feb 6 '13 at 1:15
@Joseph: To your first question: no, two geodesic edges are supposed to be the building blocks of longer geodesics. I only wanted to make the 2-edge-case clear in advance. To your second: Two consecutive edges are not a pre-geodesic because they are not a unique shortest path. – Hans Stricker Feb 6 '13 at 17:56