Every tournament conatins a hamiltonian path - question about the proof

Question

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?

Answer 1

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.

Answer 2

Think of it this way: take a line segment with $k$ points on it, corresponding to the $k$ nodes in $P$. Color a point $p$ red if $(w, p)$ is an arc, or blue if $(p, w)$ is an arc.

The first two parts state that the leftmost point is blue, and the rightmost point is red. Therefore there is some sub-segment colored (blue, red). We can stick $w$ into this point in the path.