How many shortest paths can a graph have?

90 paths, 42 paths, or 30: the answer changes with the geometry. A shorter proof leads to sharper questions—and a separate audit of the proposed improvements.

Math Referee editorial

Imagine a road network in which at most six roads meet at any junction. Two junctions are four steps apart. How many shortest routes can connect them?

The answer depends strongly on the geometry. For simple graphs, the exact maximum is 90. Requiring the graph to be planar reduces it to 42. Requiring a simplicial triangulation of the sphere reduces it to 30.

These are counts between a fixed pair of vertices, with maximum degree at most six. Edges all have unit length. The distinction matters: weighted networks or parallel edges pose different questions.

The starting point is Benjamini and Tzalik's short paper, On the number of shortest paths in graphs. It illustrates two kinds of mathematical improvement: explaining an existing bound more economically, and asking what extra structure buys us.

Count in both directions

Keep only edges that lie on a shortest path from $x$ to $y$. The resulting graph has successive distance layers. At an internal vertex $v$, let $d^-(v)$ count the incoming edges and $d^+(v)$ the outgoing ones.

Both types share the same degree budget:

$$d^-(v)+d^+(v)\le\Delta, \qquad d^-(v)d^+(v)\le \left\lfloor\frac{\Delta}{2}\right\rfloor \left\lceil\frac{\Delta}{2}\right\rceil=:q.$$

Now choose a shortest path by walking forward, uniformly choosing an edge to the next layer. Do the same in reverse from $y$. These give two probability distributions $Q_+$ and $Q_-$ on the same set of paths.

For every path $P$, their geometric mean is at least

$$\sqrt{Q_+(P)Q_-(P)} \ge\frac{1}{\sqrt{d_H(x)d_H(y)}\,q^{(t-1)/2}}.$$

Cauchy–Schwarz says the sum of those geometric means is at most one. Consequently,

$$n_G(x,y)\le\sqrt{d_H(x)d_H(y)}\,q^{(t-1)/2} \le\Delta q^{(t-1)/2}.$$

The argument exposes the constraint: branching toward one endpoint consumes degree that cannot also be used to branch toward the other.

The general degree-sensitive bound belongs to Benjamini and Tzalik. The later paper by Jing Yu and Jie-Xiang Zhu, The Maximum Number of Shortest Paths in Graphs, uses the two directional distributions to determine the exact multigraph and simple-graph maxima. Their Theorem 1.5 gives the unrestricted value 90 above. Those exact general answers should be credited to them.

Planarity restricts how paths can merge

The supplied improvement notes ask a more geometric question. In a simple planar geodesic graph, a vertex can have at most two children that also have another parent. Three such children would create a $K_{3,3}$ minor after contracting the appropriate lower and upper portions of the graph.

This restriction makes weighted forward and backward walks useful. The weights distinguish private branches from shared ones. Instead of allowing all branching patterns compatible with the degree budget, the argument accounts for which patterns can actually occur in the plane.

The resulting upper and lower bounds show that, as the degree budget grows, the exponential growth rate of the largest possible path count is $\sqrt{\Delta}(1+o(1))$. Here one first takes the distance-limsup for each fixed degree, then lets the degree grow. This does not determine the exact rate at every fixed degree.

The square-root order alone is not a novelty claim. Dvořák and Mohar's earlier planar spectral-radius estimate, combined with the Chebyshev argument, already gives that order with a weaker leading constant. The proposed gains here concern the sharper constant and the exact small-distance bounds; their priority still needs a wider literature check.

At distance four, a more direct interface count gives exact answers:

Graph class Exact maximum at distance four Degree range
Simple planar graphs $\Delta(\Delta+1)$ $\Delta\ge4$
Simplicial triangulations of the sphere $\Delta(\Delta-1)$ $\Delta\ge6$

For example, the planar degree-six construction has 18 middle vertices reached by one route from each end, and six reached by two routes from each end. Its count is

$$18\cdot1^2+6\cdot2^2=42.$$

The spherical construction has six middle vertices of each type, giving $6\cdot1^2+6\cdot2^2=30$. Explicit constructions and upper bounds are both needed to call these maxima exact.

What the audit checked

The improvement notes were produced in two model sessions and then combined after an exchange. We subsequently sent two fixed-source packets to separate runs of five model profiles and checked the returned arguments against the supplied sources. The twelve assigned obligations cover the weighted inequality, planar minor argument, bounds and their optimization, surface link argument, lower constructions, recurrence, asymptotics and distance-four result.

The checks found two qualifications. A rounded intermediate degree expression needed an integer-parameter qualification or a direct AM–GM argument for real parameters. A construction's smallest case satisfied a degree bound without always attaining that degree exactly. Both have explicit repairs; neither changes the main conclusions discussed here.

Exact finite computations tested formulas and constructions, including their degree and distance conditions. They support the written proofs; they do not establish a universal theorem by sampling. Nor does agreement between models constitute a proof.

The wider literature may contain related or equivalent planar results. Our targeted search has not established their novelty. We present them as source-checked outcomes of this investigation, with an explicit attribution boundary, rather than announcing a priority claim.

That is the useful progression here: a clearer proof, a sharper geometric question, explicit candidate improvements, and a separate check of what the new arguments actually establish.

Follow the argument

Start with the original paper and neutral dependency graph, or open the scoped panel review for the findings, proof obligations and coverage record.

The correction note records the two repairs. The working reconstruction and supporting package make the arguments available for inspection. The broader notes include material outside this audit; the panel review identifies the checked portion precisely.

Join the Math Referee preview to see how this process can be applied to a manuscript. Signup is free; reviews are paid, with a quoted credit cap before work begins.

Cite this spotlight

If this spotlight informs your work, please cite it.

Igor Rivin. How many shortest paths can a graph have?. Math Referee, .

Download .bib
View BibTeX
@misc{rivin2026spotlight-how-many-shortest-paths,
  author = {Rivin, Igor},
  title = {{How many shortest paths can a graph have?}},
  year = {2026},
  month = {November},
  date = {2026-11-19},
  howpublished = {Math Referee},
  url = {https://mathreferee.dimensionreducers.ai/spotlight/how-many-shortest-paths/},
  note = {Paper Spotlight}
}

Take a closer look at your paper.

Explore the public reports, then join the waitlist for our invitation-only research preview. Joining is free; reviews are paid.

Join the preview waitlist