Prove that if u and v are vertices of a tournament such that $\mathrm{distance}(u, v) = k$, then $\mathrm{indegree}(u) ≥ k − 1$.

Question

Prove that if $u$ and $v$ are vertices of a tournament such that $\mathrm{dist}(u, v) = k$, then $d_{\mathrm{in}}(u)\geq k − 1$.

I tried to prove this using induction on $k$. Base case is $k=1$, for which it is true. Now we consider it true for some $n$ and prove it for $n+1$. I tried some things but couldn't reach the conclusion. I don't know if this even gives an answer.

Answer 1

You don't need induction. There is a path of length $k$ from $u$ to $v$, which has $k$ vertices not including $u$ (but including $v$). There is an edge from $u$ to the first of these vertices, but there can't be edges from $u$ to any of the others, because that would create a short-cut, giving a path of length less than $k$. So all of the remaining $k-1$ vertices on the path must have edges to $u$.