Benjamini–Tzalik maximum-shortest-paths conjecture

Benjamini and Tzalik conjectured the maximum number of shortest paths between vertices at distance $t$ in a graph of maximum degree $\Delta$. Their 2023 preprint proved a general multigraph bound but left a sharper case and the exact simple-graph problem open.

Known results

• Benjamini–Tzalik, 2023: for multigraphs, $n_G(x,y)\leq \Delta\left(\left\lfloor\frac{\Delta}{2}\right\rfloor\left\lceil\frac{\Delta}{2}\right\rceil\right)^{(t-1)/2}$.
• Benjamini–Tzalik, 2023: the bound is tight for even $\Delta$, and when both $\Delta$ and $t$ are odd.
• Benjamini–Tzalik, 2023: for simple graphs and $t\geq 3$, a sharper bound was obtained, with constructions attaining it in stated cases, but the exact extremal question remained open.

September 2026 claimed resolution

A September 2, 2026 report says the preprint The Maximum Number of Shortest Paths in Graphs confirms the proposed multigraph bound, resolves the simple-graph question, and gives equality structures and tight examples. This is a claimed resolution, not yet verified here.

Current status (as of September 2026): A new preprint claims the multigraph conjecture and the simple-graph extremal question are settled, but independent verification is pending.