Let $v,w$ be two distinct vertices in the complete graph $K_n$, where $n \geq 3$. How many walks of length 3 are there from $v$ to $w$?
It is explained as follows. Let $v, x, y, w$ be walk of length 3 from $v$ to $w$. If $x=w$ then there are $n-1$ choices for $y \neq w$. if $x \neq w $ then there are $n-2$ choices for $x \neq v, w$. So, total the number of choices is $n-1 + (n-2)^2 = n^2 -3n +3$.
I get the $n-1$ part because a vertex cannot go to itself since there are no loops in a complete graph. But how do we get the other part?
Best Answer
As in the quoted solution, consider $2$ cases . . .
Case $(1):\;x=w$.
Then $y$ can be any vertex other than $w$, so $n-1$ choices.
Case $(2):\;x \ne w$.
Then there are $n-2$ choices for $x$ since by assumption, $x \ne w$, and also, we can't have $x=v$, but all other choices are possible.
Once $x$ is chosen, $y$ can't equal $x$, and $y$ can't equal $w$, but all other choices are possible, so there are $n-2$ choices for $y$.
Thus, case $(2)$ yields $(n-2)^2$ choices.
Summing the results for the two cases, the number of walks of length $3$ from $v$ to $w$ is $$(n-1)+(n-2)^2 = n^2-3n+3$$