The tournament involves 2k tennis players they play the tournament, each played with each exactly once .What is the minimum number of rounds you

Question

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.

Answer 1

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.

Answer 2

To prove that $k$ rounds does not force a triangle, consider the following set of matchesamong $2k$ players:

Divide the players $P_i: i = 1 \ldots 2k$ into equi-numerous groups $A = \{P_i : i \leq k\}$ and $B = \{P_i : i > k\}$. Then consider the following $k$ rounds of matches:

Every player in $A$ has played a match against each player in $B$ and no other match.

It is easy to show in that case that every player in $B$ has also played $k$ matches. So this is $k$ full rounds.

Yet this has no triangles.