On the Number of Shortest Paths in Graphs

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