On the Number of Shortest Paths in Graphs

Abstract

It is proved that the number of shortest paths between two vertices of distance $t$ in a graph with degrees bounded by $\Delta$ is at most $2\cdot (\frac{\Delta }{2}{)}^t$. This improves upon the naïve $\Delta (\Delta -1{)}^{t-1}$ bound.

4 pages