Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

enter image description here

from having geodesics.

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

enter image description here

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):

enter image description here

  • Is this gallery essentially complete?

  • If so: how to prove it?


  • 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?

share|improve this question
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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.