0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.