0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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 ? $\endgroup$ – Manuel Lafond Feb 1 '16 at 4:59
  • $\begingroup$ @ManuelLafond It doesn't complete the proof, because in that set some other vertex could have out-degree at least $50$ $\endgroup$ – nan Feb 1 '16 at 20:37
  • $\begingroup$ hey @nan i found your question totally by accident and it looks pretty old, did you find solution to this problem? $\endgroup$ – Krzysztof Lewko Jul 29 '16 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.