# Tournament graph with strong vertex in any subset

Consider a tournament graph with $110$ vertices. In any set of $55$ vertices, there exists a vertex that has an out-edge to at least $50$ of the remaining $54$ vertices. Prove that there exists a vertex that has an out-edge to at least $105$ of the remaining $109$ vertices.

We can start by supposing for contradiction that every vertex has out-degree at most $104$. Then for any vertex, there exists a subset of size $55$ such that that vertex has out-degree at most $49$, which means some other vertex has to have out-degree at least $50$ in that subset.

• "Then for any vertex, there exists a subset of size $55$ such that that vertex has out-degree at most $49$". This completes the proof, no ? What is your question ? – Manuel Lafond Feb 1 '16 at 4:59
• @ManuelLafond It doesn't complete the proof, because in that set some other vertex could have out-degree at least $50$ – nan Feb 1 '16 at 20:37
• hey @nan i found your question totally by accident and it looks pretty old, did you find solution to this problem? – Krzysztof Lewko Jul 29 '16 at 19:51