# Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $$n^{k-1}$$

I've tried this formula on an example where n =5 and k = 2 and I can't even find 5 walks. Any help understanding this formula and example would be greatly appreciated. Thanks.

I think there may be a mistake in your statement, unless you allow a walk to stay in the same vertex on a step, instead of crossing an edge (but that's not the usual definition of walk), or unless you consider each vertex in a complete graph to have a loop (but again, that's not the usual definition).

I think you could do a proof by induction on $$k$$, distinguishing the cases where $$u = v$$ and $$u \neq v$$. Denote $$A(k)$$ the number of walks of length $$k$$ from $$u$$ to $$v$$ if we suppose $$u = v$$ and $$B(k)$$ if we suppose $$u \neq v$$.

• the base cases are as follow:

• $$A(1) = 0$$ (there is no edge from $$u$$ to itself); $$A(2) = n-1$$ (a $$2$$-walk is $$u-w-u$$, with $$w\neq u$$);
• $$B(1) = 1$$ (there is exactly one edge from $$u$$ to $$v$$); $$B(2) = n-2$$ (a $$2$$-walk is $$u-w-v$$ with $$w\neq u$$ and $$w\neq v$$);
• the induction case can be described as such: a walk of length $$k+1$$ from $$u$$ to $$v$$ is $$u-w\sim v$$, where $$w\sim v$$ is a walk of length $$k$$ from $$w$$ to $$v$$.

• if $$u = v$$, then $$w\neq u$$ and $$w\neq v$$, and there are $$n-1$$ choices for $$w$$. That means that $$A(k+1) = (n-1) B(k)$$;
• if $$u \neq v$$, then $$w\neq u$$, but $$w$$ could be equal to $$v$$. Distinguishing the cases $$v = w$$ and $$v\neq w$$, we get $$B(k+1) = A(k) + (n-2)B(k)$$.

Combining the two, we get $$B(k+1) = (n-1)B(k-1) + (n-2)B(k)$$. This is a constant-recursive sequence of order $$2$$.

Solving this, we get an expression $$B(k) = \alpha(-1)^k + \beta(n-1)^k$$. Since $$B(1) = 1$$ and $$B(2) = n-2$$, that means that $$\alpha = -\frac{1}n$$ and $$\beta = \frac1n$$. We conclude that: $$B(k) = \frac1n((n-1)^k - (-1)^k)\qquad A(k) = \frac1n((n-1)^k+(-1)^k(n-1))$$ This is indeed an integer.

For example, the number of walks of length $$3$$ in a complete graph of order $$5$$ from the vertex $$1$$ to the vertex $$3$$ is $$\frac15(4^3-(-1)^3) = \frac{65}5 = 13$$. Indeed, those walks are: $$1013, 1023, 1043, 1203, 1213, 1243, 1303, 1313, 1323, 1343, 1403, 1413, 1423$$