# Is there always only one unique shortest path between any two nodes in a Kautz di-graph ? If yes, why ? If no, why not?

My intuition tells me that there is always a unique, single shortest path between any two nodes in a Kautz di-graph. Is this true ? If yes, why? If not, why not ?

My intuition is based on the fact that Kautz graphs are best known optimal degree-diameter digraphs, that is, for a given degree (d>2) and diameter the Kautz graphs are the largest known graphs. So in this sense, one could argue that Kautz graphs do not "waste" shortest path connections.

For two nodes labeled $w_1$ and $w_2$ there will always be a largest $n$ such that the last $n$ symbols in $w_1$ are the same as the first $n$ symbols in $w_2$. The unique shortest path from $w_1$ to $w_2$ then arises by shifting in the rest of the symbols in $w_2$ one by one -- clearly doing anything else will just send us on a detour.
In the particular case that $n=0$ we just need to check that we're allowed to start by shifting in the first symbol of $w_2$ -- but the only reason we wouldn't be would be if the first symbol of $w_2$ is the same as the last symbol of $w_1$, and then $n$ would be at least $1$.