I have the following problem: $n$ teams participate in a tournament, where everyone can play against everyone (teams obviously can't play themselves). $n + 1$ matches have already been played. Show that there is at least one team, that has played at least $3$ matches.
I've been stuck on this problem for a time now, although it feels intuitive and there should be a rather easy proof for this. I think I have found one, but I am not quite sure.
I thought about the handshake lemma, which for this case would give me the following: $\sum_{i=1}^n deg(v_i) = 2(n + 1)$. If I assume the opposite, where there are no vertices with a degree of at least three, then on the left-hand side of the handshake lemma I would basically have $n$ terms, all of which less than 3. The biggest sum this could possibly result in would be $2n$, when all vertices have a degree of 2. However, this would still leave me two short. Would this be a valid argument/proof?
Your argument seems to work OK. Another way:
Each match is a "team event" for the two participating teams. So there have been a total of $2(n+1)$ "team events" for the $n$ teams. Now apply the strong pigeonhole principle.