Exercise 2.3.21

A vertex $v$ in a tournament is called a king if $v$ can reach all other vertices within two steps. That is, for all vertex $u$ other than $v$, we have either $v\to u$ or $v\to w\to u$ for some $w$. So ${(A+A^2)}_{\mathit{ij}}>0$ is equivalent to that $i$ can reach $j$ within two steps. And the statement of this question also means that every tournament exists a king.

To prove this statement, we can begin by arbitrary vertex $v_1$. If $v_1$ is a king, then we’ve done. If $v_1$ is not a king, this means $v_1$ can not reach some vertex, say $v_2$, within two steps. Now we have that $d^{\text{+}}(v_2)>d^{\text{+}}(v_1)$ since we have $v_2\to v_1$ and that if $v_1\to w$ for some $w$ then we have $v_2\to w$ otherwise we’ll have that $v_1\to w\to v_2$. Continuing this process and we can find $d^{\text{+}}(v_1)<d^{\text{+}}(v_2)<\cdots$ and terminate at some vertex $v_k$ since there are only finite vertces. And so $v_k$ would be a king.