Interesting Logic Problem Proof I have no idea how to solve this problem. I've tried doing it for 5 people but am not getting anywhere in terms of the proof. 

A chess tournament had 10 participants. Each round, the participants split into pairs, and each pair played a game. In total, each participant played with every other participant exactly once, and in at least half of the games both players were from the same town. Prove that during each round there was a game played by two participants from the same town. 

 A: The problem can be restated in graph-theoretical terms:

In $K_{10}$ at least 23 edges are coloured, with the coloured edges forming a disjoint union of complete graphs. Prove that no perfect matching can avoid all of the coloured edges.

In this formulation, the vertices represent the players and the edges represent games. A coloured edge indicates a game where the players came from the same town, and because this relation is transitive we must have the "disjoint union of complete graphs" requirement. A perfect matching corresponds to a tournament round; there are nine rounds in all, but this does not matter for our proof.
What is the maximum number of edges that can be coloured while still allowing a perfect matching? The answer is 20, when the coloured edges form two copies of $K_5$. However, this is less than 23 – half of the 45 edges in $K_{10}$ – so no perfect matching avoiding the coloured edges can exist when there are at least 23 coloured edges, and no round can have only inter-town matchups if there are at least 23 same-town matchups throughout the tournament. This completes the proof.
A: Each participant played with each other participant exactly once, there were ten participants, so there were 45 (9+8+...+1) games. In at least half (at least 23) pf the games  both participants were from the same town so the 10 participants must include enough groups sharing a common town to comprise at least 23 games among the members of each group, combined. It's easy to see that groups of 4,3,3 will not work (only 10 games total) nor will 5,5 (20 games) or 6,4 (21). There must therefore be at least one group of 7 people with a common town, and since there are only 10 participants total it is impossible to have a round of five pairs without two of them meeting. 
