# Given a tournament with \$2^n\$ vertices, show that there is a sub-tournament with at least \$n + 1\$ vertices that is acyclic

So a tournament is just a complete directed graph, I believe.

I’m having trouble proving this problem. I know it is induction however. I was thinking the base case is $$2^1$$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $$2^{n + 1}$$. But I’m not sure how to approach this. Any ideas would be extremely appreciated.