$20$ football teams take part in a tournament. On the first day all the teams play one match. On the second day all the teams play a further match. Prove that after the second day it is possible to select 10 teams, so that no two of them have yet played each other.
My solution:
Note that each vertex has degree $2$ after the second day, as each vertex played twice. Then since $\sum \deg(v_i) = 2E$, there are $20$ edges. There are ${20\choose 2} = 190$ edges for every team to , and so we may choose 10 verticies, since ${10\choose2} = 45$, and...
I don't know how to finish the proof. I feel like I'm missing something obvious, but I cannot figure out what.
Thanks for the help!
Not only does each vertex have degree $2$, so that the graph is a disjoint union of cycles, but all those cycles are of even length. This can be seen by colouring edges corresponding to the first day's matches red and the second day's matches blue, then noting that all vertices are incident to one red and one blue edge.
With that in mind, a set of $10$ teams that have not played each other can be formed by picking every other team in each cycle. For example, if there is a cycle of length $6$, $t_1t_2\dots t_6$, we pick teams $t_1,t_3,t_5$.