There is a proof that every tournament contains a Hamiltonian path and it goes as follows:
Let $P$ be a path of greatest length in a tournament $T$, say $P = (v_1,v_2,…,v_k)$. Let's say that there exist a vertex $w$ not on $P$. Clearly neither $(w,v_1)$ nor $(v_k,w)$ are not arcs of the tournament because then $P$ could be made longer. So $(v_1, w),(w,v_k)$ are arcs of $T$. This implies that there must exist a vertex $v_i$ for $1\leq i \leq k-1$ such that $(v_i,w)$ is an arc of $T$ and $(w,v_{i+1})$ is an arc of $T$ (…)
I don't understand this last claim. Why exactly can we make it?
Best Answer
Let $I$ be the set of $i\in\{1,\ldots,k\}$ such that $(v_i,w)$ is an arc of $T$. We know that $I\ne\varnothing$, because $1\in I$. Let $m=\max I$; we know that $m<k$, because $k\notin I$. Therefore $1\le m\le k-1$, $(v_m,w)$ is an arc of $T$, and $(v_{m+1},w)$ is not an arc of $T$. But one of $(v_{m+1},w)$ and $(w,v_{m+1})$ must be an arc of the $T$, so $(w,v_{m+1})$ is an arc of $T$, and $v_m$ and $v_{m+1}$ are the desired vertices.