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

The manuscript bounds the number of shortest paths by combining two entropy expansions and a bound on incoming/outgoing degree products. It then discusses extremal examples, simple graphs, random walks, girth, sphere triangulations and higher-dimensional fillings. This map records the original 2023 text and its argument structure; later developments and assessments are separate.

Source SHA-256: `1e30c660370d3327db605338b6064452b6ceb7949338d7c2315c2ada33faee5e`. Indexed 16,939 characters.

Edges point from prerequisite to consumer. Solid proof edges are attributed inferences, not formal certificates; references remain candidates.

## 1\. Geodesic support and the degree budget

Identify the relevant edges before counting paths.

Claims: argument:geodesic-support, argument:degree-product

## 2\. The main entropy argument

Combine directional conditional entropies into the shortest-path estimate.

Claims: argument:two-entropy-expansions, thm:counting_shortest_paths

## 3\. Examples and refinements

Read the proposed equality cases, simple-graph bound, random-walk statement and girth discussion separately.

Claims: construction:alternating-cycle, conjecture:line:167:8127, remark:simple-graphs, construction:simple-cycle-blowup, question:line:181:10522, remark:random-walk, remark:large-girth

## 4\. Surface geometry and fillings

Track the geometric degree reduction separately from the higher-dimensional questions.

Claims: argument:surface-degree-reduction, proposition:line:195:13057, definition:minimal-filling, conjecture:line:208:14800, question:line:213:15127

## Internal claim index

### Theorem 1 — `thm:counting_shortest_paths`

Source lines 89–92.

Degree-sensitive shortest-path bound

Restrict to the geodesic graph, express path-count logarithm as entropy, expand from both directions and control internal degree products.

- `argument:two-entropy-expansions` (proof_dependency; source_audit_annotation): Finally, by plugging everything into \Cref{eq:chain_rule_both_directions}:
- `argument:degree-product` (proof_dependency; source_audit_annotation): Plugging \Cref{eq:log_degree_bound} into \Cref{eq:expanding_terms_in_entropy_sum} we get

### Conjecture 2 — `conjecture:line:167:8127`

Source lines 167–169.

Odd-degree, even-distance conjecture

The conjecture asks whether the alternating-multiplicity cycle supplies the maximum when the degree is odd and the distance is even.


Candidate references: `construction:alternating-cycle` (internal_reference).

### Question 3 — `question:line:181:10522`

Source lines 181–183.

Exact simple-graph maximum

Ask for the maximum shortest-path count at a fixed degree budget and endpoint distance in simple graphs.


Candidate references: `remark:simple-graphs` (internal_reference).

### Proposition 4 — `proposition:line:195:13057`

Source lines 195–198.

Triangulated-sphere bound

Seek a degree budget reduced by two at internal geodesic vertices, then apply the main counting method.

- `thm:counting_shortest_paths` (proof_dependency; source_audit_annotation): Notice that combining this with the bound in \Cref{thm:counting_shortest_paths} yields the claim.
- `argument:surface-degree-reduction` (proof_dependency; source_audit_annotation): We claim that $\forall v \neq x,y$ we have $deg_x(v)+deg_y(v) \leq \Delta-2$. Notice that combining this with the bound in \Cref{thm:counting_shortest_paths} yields the claim. Let $N$ be the set of neighbors of $x$, and assume $v \in N$. It is well known (e.g. can be proved by excision) that the graph induced on $N$ is a cycle (by excision it has the homology of the cycle and hence it is a cycle), therefore $v$ has two edges to neighbors in $N$ which are not in $N_x(v) \cup N_y(v)$, hence $\mid N_x(v) \cup N_y(v) \mid \leq \Delta-2$ as needed. By contracting $N$ towards $x$ the same inequality holds for the $2$-neighbourhoods of $x$, and by induction for all $v \neq x,y$ that lie along a path from $x$ to $y$.

Candidate references: `thm:counting_shortest_paths` (candidate_proof_dependency).

### Conjecture 5 — `conjecture:line:208:14800`

Source lines 208–210.

Higher-dimensional filling conjecture

Ask for a uniform upper bound on the number of minimum-size fillings in a bounded-incidence simplicial complex.


Candidate references: `definition:minimal-filling` (internal_reference).

### Question 6 — `question:line:213:15127`

Source lines 213–215.

Bernoulli-weighted cubical filling question

Assign independent Bernoulli face weights in the cubical lattice and ask about the typical number of minimal fillings.


Candidate references: `definition:minimal-filling` (internal_reference).

### Geodesic support — `argument:geodesic-support`

Source lines 103–103.

Restrict the graph to the union of shortest paths between the chosen endpoints, then record successive vertices and edges.

### Two entropy expansions — `argument:two-entropy-expansions`

Source lines 123–126.

Write the entropy of a uniform shortest path from each endpoint and combine the directional conditional-entropy terms.

- `argument:geodesic-support` (proof_dependency; source_audit_annotation): Without loss of generality assume every edge and vertex in $G$ belong to some shortest path between $x$ and $y$.

### Degree-product bound — `argument:degree-product`

Source lines 142–146.

Use the disjoint incoming and outgoing edge sets at an internal geodesic vertex to bound their product under the common degree budget.

- `argument:geodesic-support` (proof_dependency; source_audit_annotation): Note that $N_x(v),N_y(v)$ are disjoint as an edge in the intersection will imply that there is a vertex appearing twice along a shortest path which is absurd. Hence since the graph is of degree bounded by $\Delta$ we have that $deg_x(v)+deg_y(v)\leq \Delta$, hence: \begin{equation}\label{eq:log_degree_bound} \log( deg_x(v) deg_y(v)) \leq \log \left( \lfloor \frac{\Delta}{2} \rfloor \cdot \lceil \frac{\Delta}{2} \rceil \right). \end{equation}

### Alternating-multiplicity cycle — `construction:alternating-cycle`

Source lines 161–162.

Alternate two edge multiplicities around an even cycle and count the two directions between antipodal endpoints.

### Weighted random-walk remark — `remark:random-walk`

Source lines 171–173.

The paper proposes transferring a multigraph path count to a bound for a weighted random walk.


Candidate references: `thm:counting_shortest_paths` (internal_reference).

### Simple-graph refinement — `remark:simple-graphs`

Source lines 175–175.

Exploit the unique first and last edges at the internal endpoint layers to modify the entropy estimate.

- `argument:two-entropy-expansions` (proof_dependency; source_audit_annotation): \paragraph{Simple graphs} Note that a slightly stronger bound applies to simple graphs. In case $t = 1$ we have $n_G(x,y)\leq 1$ since simple graphs have no parallel edges. In case $t=2$ one has $n_G(x,y)\leq \Delta$ since again, the collection of $2$-paths from $x$ to $y$ must have disjoint midpoints by simplicity. For $t \geq 3$, one gets a bound sharper by $\approx \frac{\Delta}{4}$ factor. This is obtained by observing that $H(E_1 \mid X_1)=0$ (there's a unique edge going from $X_1$ to $X_0=x$ by simplicity), hence $H(E_1 \mid X_1)+ H(E_2 \mid X_1) \leq \log(\Delta-1)$. Applying this improved bound to the first and last terms of the sum \Cref{eq:chain_rule_both_directions} gives: $n_G(x,y) \leq \Delta (\Delta-1) \cdot \left(\lfloor \frac{\Delta}{2} \rfloor \lceil \frac{\Delta}{2} \rceil \right)^{(t-3)/2}$.

### Simple cycle-blowup example — `construction:simple-cycle-blowup`

Source lines 177–179.

Replace cycle vertices by independent sets and cycle edges by bipartite interfaces, then count antipodal shortest paths.

### Large-girth discussion — `remark:large-girth`

Source lines 191–191.

Use uniqueness near the endpoints and compare it with a proposed layered construction using high-girth bipartite interfaces.

- `argument:degree-product` (proof_dependency; source_audit_annotation): \paragraph{Large girth}   It is plausible to suspect that assuming large girth one may get a much better upper bound. While large girth does imply an improved bound, it improves the exponent, but not the base of the exponent. If a graph $G$ has girth strictly bigger than $g$ then one can shave off the exponent by roughly $\Theta(g)$ (additive). This follows similarly to the analysis in the case of simple graphs, by noticing that each vertex $v$ in the $\frac{g}{2}$ neighborhood around $x$ has $deg_x(v)=1$ (otherwise a cycle is formed by $v$, two elements in $N_x(v)$ and the paths from them towards $x$) hence the entropy bounds in $\Cref{eq:log_degree_bound}$ are sharper for the edges lying in the $\frac{g}{2}$ neighborhoods of $x,y$. A construction of a graph with $(\frac{\Delta}{2})^{t-\Theta(g)}$ can be made similarly to the simple graph construction: Instead of replacing each edge of a cycle of length $2t$ by a bi-clique with $\frac{\Delta}{2}$ vertices on each side one replaces each edge by a bi-regular graph of degree $\frac{\Delta}{2}$ and large girth.

### Surface degree-reduction argument — `argument:surface-degree-reduction`

Source lines 201–203.

The printed proof discusses neighboring vertices and a contraction to obtain a degree budget reduced by two.

### Minimal fillings — `definition:minimal-filling`

Source lines 206–206.

Define irreducibility and minimum filling size over the two-element field before posing the higher-dimensional conjecture.

## External inputs and references

### [BR10] Babu2010AnEB — `external:Babu2010AnEB`

Source lines 225–231.

Ajesh Babu and Jaikumar Radhakrishnan. \newblock An entropy based proof of the moore bound for irregular graphs. \newblock {\em ArXiv}, abs/1011.1058, 2010. \newblock URL: \url{https://api.semanticscholar.org/CorpusID:18756806}.

The original introduction describes this as an antecedent for the entropy proof strategy, not an imported theorem supplying the stated bound.

Role: **background**. Our proof is based on analyzing the entropy of a uniformly random shortest $x$ - $y$ path and resembles the entropy proof of the irregular Moore bound by Babu and Radhakrishnan


Candidate references: `manuscript` (external_reference).

### [DCKN{\etalchar{+}}20] FirstPassage — `external:FirstPassage`

Source lines 231–239.

Hugo Duminil-Copin, Harry Kesten, Fedor Nazarov, Yuval Peres, and Vladas Sidoravicius. \newblock On the number of maximal paths in directed last-passage percolation. \newblock {\em Ann. Probab.}, 48(5):2176--2188, 2020. \newblock \href {https://doi.org/10.1214/19-AOP1419} {\path{doi:10.1214/19-AOP1419}}.

A one-dimensional analogue cited beside the filling question.

Role: **background**. For a one dimension analogue see \cite{FirstPassage}.


Candidate references: `section:2` (external_reference).

### [MW09] MeshulamW09 — `external:MeshulamW09`

Source lines 239–246.

Roy Meshulam and N.~Wallach. \newblock Homological connectivity of random k-dimensional complexes. \newblock {\em Random Struct. Algorithms}, 34(3):408--417, 2009. \newblock URL: \url{https://doi.org/10.1002/rsa.20238}, \href {https://doi.org/10.1002/RSA.20238} {\path{doi:10.1002/RSA.20238}}.

The manuscript cites related higher-dimensional definitions; no theorem is imported into its graph counting proof.

Role: **background**. For related definitions see \cite{MeshulamW09}


Candidate references: `section:2` (external_reference).

### [RY20] rao_yehudayoff_2020 — `external:rao_yehudayoff_2020`

Source lines 246–253.

Anup Rao and Amir Yehudayoff. \newblock {\em Communication Complexity: and Applications}. \newblock Cambridge University Press, 2020. \newblock \href {https://doi.org/10.1017/9781108671644} {\path{doi:10.1017/9781108671644}}.

Cited by the original authors for an exposition of the entropy method.

Role: **background**. See \cite{rao_yehudayoff_2020} for a nice presentation of the proof.


Candidate references: `manuscript` (external_reference).

## Coverage and limits

{"mode": "native_latex_index", "claims": 16, "sections": 2, "external_references": 4, "source_bibliography_entries": 4, "unresolved_bibliography": 0, "unresolved": 0}

- Reference edges are not certified proof dependencies. Edge direction is prerequisite → consumer.
- Numbers reflect simple source counters; labels and line anchors are authoritative.
- Extractive statements and proof openings are marked; they are not reconstructed proof gists.
- Macros, included files and custom counters require an expanded source or annotated fallback.
- The ten unnumbered argument/comment nodes were added from exact quotations in the original text; their gists describe the source rather than adjudicate it.
- The original Section 1 is not wrapped in a proof environment, so its attributed proof dependencies were added explicitly with literal source evidence.
- All four original bibliography entries are indexed. Their original citation roles are background or related context; this export does not audit their full contents.
- Later papers and the 2026 reconstruction are not inserted into the original-paper dependency map.
