The tournament involves $2k$ tennis players they play the tournament, each played with each exactly once. What is the minimum number of rounds you need to play to find 3 such that everyone plays with everyone?
In each round, $k$ games are played. I proved that if $k ^ 2 + 1$ edges will be drawn in a graph of $2k$ vertices, then a triangle is sure to exist, that is, if $k + 1$ round is held. And how to prove that $k$ rounds is not enough, I did not understand, I predict that this is proved by induction.
Best Answer
Make a bipartite graph $K_{k,k}$, here we have $k^2$ edges and no triangles.
So you have two groups of size $k$ with no plays beteween players in the same group and each pair or players from different group played a game. So $k^2+1$ is a minimum.
One way to see that $k^2+1$ works is to use Turan theorem, which says that if graph on $n$ vertices doesn't have a triangle, then $\varepsilon \leq {n^2\over 4}$. But of course, this could be easly proved with induction with no use of Turan.