We have a connected graph \(G = (V,E)\) with maximum degree \(\Delta\), equipped with:
- a graph metric \(d_G\) (shortest-path distance), and
- some auxiliary metric \(d'\) on \(V\).
For vertices \(x,y \in V\), let \[ P_G(x,y) \] denote the number of distinct geodesics (shortest paths) from \(x\) to \(y\) in \(G\). This note records a simple branching bound and then specializes it to the permutohedron, where the geometry is particularly relevant for sorting.
General Branching Bound
Let \(G = (V,E)\) be a connected graph with maximum degree \(\Delta\). For each pair \(x,y \in V\), write \(d_G(x,y)\) for the graph distance and \(P_G(x,y)\) for the number of distinct geodesics from \(x\) to \(y\). Then \[ P_G(x,y) \le \] \[ \Delta\,(\Delta - 1)^{d_G(x,y)-1}. \]
Fix \(x,y \in V\) and set \[ k = d_G(x,y). \] Any geodesic from \(x\) to \(y\) is a sequence \[ x = v_0, v_1, \dots, v_k = y \] with \(v_i\) adjacent to \(v_{i+1}\) and total length \(k\).
At the first step there are at most \(\Delta\) choices for \(v_1\), since \(v_1\) must be a neighbor of \(x\). At each subsequent step \(i = 1,\dots,k-1\), the vertex \(v_{i+1}\) must be chosen among neighbors of \(v_i\) that keep the remaining distance to \(y\) on track to reach \(k\) in total.
More concretely, for a geodesic we must have \[ d_G(v_i,y) = k - i \] \[ \quad\text{and}\quad \] \[ d_G(v_{i+1},y) = k - (i+1). \] Among the neighbors of \(v_i\), at most one can satisfy \[ d_G(u,y) = d_G(v_i,y) + 1, \] which would move strictly away from \(y\). That neighbor, if it exists, cannot lie on any geodesic of length \(k\). Thus at each intermediate step there are at most \(\Delta - 1\) valid choices for \(v_{i+1}\).
Counting possibilities gives \[ P_G(x,y) \le \] \[ \Delta(\Delta-1)^{k-1} = \] \[ \Delta(\Delta-1)^{d_G(x,y)-1}, \] as claimed.
The bound is elementary and not intended as a new result; its value here is in making the branching structure of geodesics explicit for later use on the permutohedron.
Main Theorem: Geodesics on the Permutohedron
Now specialize to the permutohedron \(G_n\), the Cayley graph of \(S_n\) with edge set given by adjacent transpositions. Let \(d_K\) denote Kendall distance, i.e., the minimum number of adjacent transpositions needed to transform one permutation into another.
Let \(G_n\) be the permutohedron on \(S_n\) with edges given by adjacent transpositions, and let \(d_K\) denote Kendall distance. For permutations \(\pi_a,\pi_b \in S_n\), let \(P_{G_n}(\pi_a,\pi_b)\) be the number of distinct geodesics between them in \(G_n\). Then \[ P_{G_n}(\pi_a,\pi_b) \;\le\; \] \[ (n-1)\,(n-2)^{d_K(\pi_a,\pi_b)-1}. \]
In \(G_n\), each vertex has degree \[ \Delta = n-1, \] since there are \(n-1\) adjacent positions where a transposition can be applied. Moreover, the graph distance coincides with Kendall distance: for all \(\pi_a,\pi_b \in S_n\), \[ d_G(\pi_a,\pi_b) = d_K(\pi_a,\pi_b), \] because both are defined as the minimum number of adjacent transpositions required to transform \(\pi_a\) into \(\pi_b\).
Set \[ k = d_G(\pi_a,\pi_b). \] By the identity above, \[ k = d_G(\pi_a,\pi_b) = \] \[ d_K(\pi_a,\pi_b). \] Applying the general branching bound from the proposition with this \(\Delta\) and \(k\) gives \[ P_{G_n}(\pi_a,\pi_b) \;\le\; \] \[ \Delta\,(\Delta-1)^{k-1}. \] Substituting \(\Delta = n-1\) and \(k = d_K(\pi_a,\pi_b)\), we obtain \[ P_{G_n}(\pi_a,\pi_b) \le \] \[ (n-1)\,(n-2)^{d_K(\pi_a,\pi_b)-1}, \] which is the desired bound.
This is the main point of the note: a clean, explicit bound on geodesic multiplicity on the permutohedron in terms of Kendall distance.
Hamming-Distance Corollary
For some purposes it is convenient to express the bound in terms of Hamming distance between permutations.
Let \(H(\pi_a,\pi_b)\) denote the Hamming distance between permutations \(\pi_a,\pi_b \in S_n\). Then \[ P_{G_n}(\pi_a,\pi_b) \le \] \[ (n-1)\,(n-2)^{(n-1)H(\pi_a,\pi_b)-1}. \]
It is standard that Kendall distance is bounded above by a multiple of Hamming distance: \[ d_K(\pi_a,\pi_b) \;\le\; \] \[ (n-1)\,H(\pi_a,\pi_b), \] since each symbol in the wrong position can be moved into place using at most \(n-1\) adjacent swaps.
Combining this with the theorem gives \[ P_{G_n}(\pi_a,\pi_b) \le \] \[ (n-1)\,(n-2)^{d_K(\pi_a,\pi_b)-1} \le \] \[ (n-1)\,(n-2)^{(n-1)H(\pi_a,\pi_b)-1}, \] which is the claimed inequality.
The Hamming-distance version is deliberately coarse, but can be more convenient when Kendall distance is not already in use. In the sorting-as-gradient-flow picture, these bounds provide a simple way to think about how “wide” the family of discrete shortest paths can be between two permutations at a given distance.