There are $2n-1$ two-element subsets of set $\{1,2,...,n\}$. Prove that one can choose $n$ out of these such that their union contains no more than $\frac{2}{3}n+1$ elements.
I was trying this one too and with no success. Then I read the official solution (page 10, problem 5) and it is a kind of not natural to me. Can someone try to walk another way?
We are given a graph $G = (V, E)$ where $V = \{v_1,\dots,v_n\}$ and $|E| = 2n - 1$. What we are trying to do is to remove as few edges as possible to leave as many isolated vertices as possible. To do this, we try to find a vertex of least degree and remove its edges.
The degree formula says that
$$ \sum_{i = 1}^n \deg(v_i) = 2|E| = 4n - 2. $$
It follows that there is a vertex in $G$ of degree $\le 3$. If every vertex had degree $\ge 4$ then $\sum_{i = 1}^n \deg(v_i) \ge 4n$, which is impossible.
Without loss of generality, let this vertex be $v_n$. Then form the graph $G_1 = G\setminus v = (V_1, E_1)$. Now $|E_1| \ge 2n - 4$. Again by the degree formula we have
$$ \sum_{i = 1}^{n - 1} \deg(v_i) = 2|E_1| \ge 4(n - 1) - 4 \tag{1}$$
We want to conclude that there is a vertex of degree $\le 3$. To conclude this, we would like to have an equality in $(1)$. To achieve this we allow ourselves to remove exactly three edges at each step (which might be more than the degree of the vertex we removed). Doing this, we have $2|E_1| = 4(n - 1) - 4$ and we get a vertex of degree $\le 3$.
Inductively, suppose we remove the vertices $v_{n - k + 1}, \dots, v_n$ (after possibly relabeling) and $3k$ edges to get the graph $G_k = (V_k, E_k)$ where $|E_k| = 2n - 1 - 3k$. Then we have
$$ \sum_{i = 1}^{n - k} \deg(v_i) = 2|E_k| = 4(n - k) - 2 - 2k $$
so there is a vertex of degree $\le 3$.