A directed bichromatic tournament

Question

Consider a tournament with $n$ vertices. Each edge of the directed complete graph (tournament) is colored red or blue. Prove there exist a vertex for which there exists a monochromatic path from it to any other vertex.

My method: Let $S=\{1,2,...,n\}$ where they are the vertices. Use induction on n. By inductive hypothesis, WLOG x is connected to $S\ \{X,y\}$ via a monochromatic path without edges from $y$. Note $y$ is unique or I am done. So every vertex is not connected to exactly one via a monochromatic path. 1 would be connected to some $v$ which connects the vertex 1 was assumed to be disconnected to. Qed. Is this right? Are there other methods?

Answer 1

Theorem. Let $T$ be a (finite) tournament, and suppose each edge of $T$ is colored red or blue. Then there is a vertex $x$ such that, for every vertex $y$, there is a monochromatic (directed) path from $x$ to $y$.

Proof. Assume for a contradiction that $T$ is a minimal counterexample. For each vertex $x$ of $T$ we can choose a vertex $f(x)\ne x$ such that there is a monochromatic path from $f(x)$ to every vertex of $T-x$ but there is no monochromatic path from $f(x)$ to $x$; of course this implies that there is a directed edge $x\to f(x)$. Since $T$ is finite, there is a cycle $x_1,\dots,x_n,x_1$ such that $f(x_i)=x_{i+1}$ for $i=1,2,\dots,n-1$, and $f(x_n)=x_1$.

If the edges $x_1x_2,x_2x_3,\dots,x_nx_1$ are all the same color, we get an obvious contradiction, since there is then a monochromatic path from $x_2$ to $x_1$. Therefore the cycle must contain two consecutive edges of different colors. Without loss of generality, suppose $x_1x_2$ is red and $x_2x_3$ is blue. Now there is a monochromatic path from $x_3$ to $x_1$. If there is a red path from $x_3$ to $x_1$, then there is a red path from $x_3$ to $x_2$; if there is a blue path from $x_3$ to $x_1$, then there is a blue path from $x_2$ to $x_1$; in either case we have arrived at a contradiction.