Number of paths between any two distinct vertices is always same?

Question

I've encountered this probably really easy problem.

"Let u, v, and w be any distinct vertices in $\ K_n $, for $\ n \geq 3 $. Then, the number of simple distinct paths from u to v and u to w is same."

I get this must be true intuitively and I can count them easily, but I was wondering if there is any proof that doesn't involve directly counting the number of paths.

Thanks!

Answer 1

The complete graph $K_n$ has automorphisms sending $(u,v)$ to $(u,w)$ for any $u,v,w$ and $n\ge3$. Such automorphisms (any one can be chosen for the purpose of this proof) act on any simple path from $u$ to $v$, turning it into a path from $u$ to $w$, giving a bijection between the simple paths from $u$ to $v$ and those paths from $u$ to $w$. Thus the two numbers of paths must be equal.