Exercise 17. Let $\mathrm{k}, \mathrm{n} \geqslant 1$ be two fixed integers. Thanima had $2 \mathrm{n}$ candies of each color. She gave two candies of different colors to each of the children in her family. Knowing that no matter how $k+1$ children are chosen, there are two among them who received a candy of the same color, find the maximum possible number of children.
Solution to Exercise 17 We can model the problem with a graph: each vertex of this graph is a color. If Thanima gave a candy of color $\mathrm{c}_{1}$ and a candy of color $\mathrm{c}_{2}$ to a child in her family, we add an edge between $\mathrm{c}_{1}$ and $\mathrm{c}_{2}$.

Since Thanima has only $2 \mathrm{n}$ candies of each color, the maximum degree of each vertex is $2 \mathrm{n}$. We also know that it is impossible to choose $k+1$ disjoint edges. We are looking for the maximum number of edges.

We see that it is possible to obtain $3 \mathrm{kn}$ edges. For this, we create a graph in which we place $\mathrm{k}$ times the following structure: we create three vertices, and between each pair of these three vertices, we add $n$ edges. Let's show that it is not possible to do more than $3 \mathrm{kn}$. For this, we consider a set $\mathrm{C}$ of disjoint edges of maximum cardinality. According to the statement, we have $|\mathrm{C}| \leqslant \mathrm{k}$. Thus, each edge of the graph must intersect one of the edges of $\mathrm{C}$, otherwise it would contradict the maximality of $\mathrm{C}$. Let $\mathrm{V}_{\mathrm{C}}$ be the set of vertices that appear in one of the edges of C. The number of edges in the graph is:

$$
\sum_{v \in V_{C}} d_{\text{ext}}(v)+\frac{d_{\text{int}}(v)}{2}
$$

where $\mathrm{d}_{\text{ext}}(v)$ is the number of edges that connect $v$ to vertices that are not in $V_{C}$, and $\mathrm{d}_{\text{int}}(v)$ is the number of edges that connect $v$ to vertices in $V_{C}$. Let $(a, b)$ be an edge of $C$, and let $x, y$ be two different vertices that are not in $V_{C}$, we cannot have both edges between $a$ and $x$ and between $b$ and $y$, otherwise replacing $(a, b)$ with $(a, x)$ and $(b, y)$ in $C$ would give a larger set of disjoint edges. Two cases can occur:

- Both $a$ and $b$ have edges to the complement of $V_{C}$, in this case, all these edges go to the same vertex, and the degree bound on this vertex gives $d_{\text{ext}}(a)+d_{\text{ext}}(b) \leqslant 2 n$.
- Or there is at most one vertex among $a$ and $b$ that has edges to the complement of $V_{C}$, in this case we also have $\mathrm{d}_{\text{ext}}(a)+\mathrm{d}_{\text{ext}}(b) \leqslant 2 \mathrm{n}$.

Since $\mathrm{d}_{\text{int}}(v) \leqslant 2 \mathrm{n}-\mathrm{d}_{\text{ext}}(v)$ for all vertices $v$, we have:

$$
\begin{aligned}
d_{\text{ext}}(a)+d_{\text{ext}}(b)+\frac{d_{\text{int}}(a)+d_{\text{int}}(b)}{2} & \leqslant d_{\text{ext}}(a)+d_{\text{ext}}(b)+\frac{4 n-d_{\text{ext}}(a)+d_{\text{ext}}(b)}{2} \\
& =2 n+\frac{d_{\text{ext}}(a)+d_{\text{ext}}(b)}{2} \\
& \leqslant 3 n
\end{aligned}
$$

Thus, by grouping the terms two by two, we obtain that the number of edges in the graph is:

$$
\sum_{v \in V_{C}} \mathrm{~d}_{\text{ext}}(v)+\frac{\mathrm{d}_{\mathrm{int}}(v)}{2} \leqslant 3 \mathrm{kn}
$$

Comment from the graders: The exercise was very little addressed.