I am taking a course on probabilistic methods in combinatorics. I couldn't solve the following exrcise:
Prove that for any tournament $T=(V, E)$ in which all outdegrees are at least 10, we can color the vertices so that every vertex at least one outneighbor of each color.
If I just color all vertices randomly, then the bound on the probability of the required property not holding is:
$$Pr(\exists v\in V \text{ all of $v$'s outneighbors are of the same color}) \\\le \sum_{v \in V}Pr(\text{all of $v$'s outneighbors are of the same color}) \\= \sum_{v \in V}(\frac{1}{2})^{\deg_{\mathrm{out}}(v) - 1} \le \sum_{v \in V}(\frac{1}{2})^{10} = n(\frac{1}{2})^{10}.$$
And this bound is not less than 1 for large $n$.
I know that I have not used the fact that $T$ is tournament, and I need to use it somehow.
My idea was to take two vertices $a, b \in V$ with large indegrees, color them by two different colors, and then every vertex who is connected to both will necessarily have outneighbors of both colors. But then I still have to worry about $a, b$ and all of their outneighbors.
I am thinking maybe there is some property of tournaments which I could use but don't know.
A probabilistic argument would be very appreciated, but just a graph-theoretic one would help as well.
Also, I am not looking for a full solution but rather for a hint, or some direction for this problem, since I really don't know where to even begin.
Theorem. Let T be a tournament of order $n$ in which all outdegrees are $\ge5;$ then the vertices can be colored with two colors so that every vertex has at least one outneighbor of each color.
Proof. Let $p$ be the probability that a random $2$-coloring of the vertices fails to have the desired property; it will suffice to show that $p\lt1.$
Let $s_1,s_2,\dots,s_n$ be the outdegree sequence. Without loss of generality, we can assume that $$s_1\le s_2\le\cdots\le s_n.$$ Then, for each $i,$ we have $$\binom i2\le s_1+s_2+\cdots+s_i\le is_i,$$ whence $$s_i\ge\left\lceil\frac{\binom i2}i\right\rceil=\left\lceil\frac{i-1}2\right\rceil.$$ Thus we have $$p\ \le\ \sum_{i=1}^n\left(\frac12\right)^{s_i-1}\lt\ \ \sum_{i=1}^9\left(\frac12\right)^4+\sum_{i=10}^\infty\left(\frac12\right)^{\left\lceil\frac{i-1}2\right\rceil-1}\ =\ \frac9{16}+\frac14\ \lt\ 1.$$