# Reading worksheet: On the Number of Shortest Paths in Graphs

Itai Benjamini and Elad Tzalik, arXiv:2311.10014v1, submitted 16 November 2023.
This worksheet accompanies the original four-page manuscript. It contains no panel verdicts.

## The question

Fix vertices $x,y$ at distance $t$ in a graph with maximum degree at most $\Delta$.
How many shortest $x$–$y$ paths can there be? Keep simple graphs, multigraphs and
weighted random walks separate. In a multigraph a path records its edge choices.

## Reconstruct the main argument

1. Describe the union of all shortest $x$–$y$ paths and its distance layers.
2. Write the entropy of a uniformly selected shortest path in each direction.
   Check the indices and conditioning variables in every displayed equality.
3. Relate the two conditional edge entropies at an internal vertex to its incoming
   and outgoing degrees. Record where the degree bound and integrality enter.
4. Check the first and last terms separately, then recover Theorem 1.

## Separate the comments

- Count the paths in the alternating-multiplicity cycle and identify the parity cases.
- For a weighted random walk, write the probability of an individual path before
  comparing it with an unweighted path count.
- For the simple-graph bound, record the hypotheses needed at distances one, two
  and at least three. Count the proposed construction independently.
- In the girth discussion, distinguish an upper estimate from a construction
  attaining its proposed order.
- For Proposition 4, distinguish the link cycle from the graph induced by all
  neighbors, and distinguish internal geodesic vertices from arbitrary vertices.
  Track the effect of any contraction on the hypotheses.
- For the final questions, record the meaning of irreducibility, minimum filling
  and the random face weights before evaluating the proposed growth statement.

## Record an independent assessment

| Source result or passage | Exact statement and hypotheses | Required inputs | Checked argument or unresolved step |
| --- | --- | --- | --- |
| Theorem 1 | | | |
| Conjecture 2 and Question 3 | | | |
| Random-walk, simple-graph and girth comments | | | |
| Proposition 4 | | | |
| Conjecture 5 and Question 6 | | | |

The interactive roadmap is a source index with attributed dependencies, not a
proof certificate. Its later publication date does not change the manuscript's
2023 edition. Assessments, proposed replacements and subsequent literature are
available separately in the panel view.
