On the Number of Shortest Paths in Graphs

Itai Benjamini, Elad Tzalik

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 th…