Graph theory in disguise? 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?
 A: 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$.
A: Finishing the previous proof as requested.
First lets summarize the main argument of that proof.  Initialize $G_0=G$.  From any $G_k$ you can form $G_{k+1}$ by removing: 


*

*$1$ node $v \in G_k$ of degree $d_v \le 3$, and of course all its $d_v$ associated edges [Note: the degree is measured in $G_k$, not the original $G$], and,

*$3 - d_v$ other edges (any other edges) of $G_k$.
[Note: it is possible, due to the second bullet, that some node becomes isolated (has no edges) and yet not removed.  This is perfectly fine.]
As a result, $G_{k+1}$ has exactly $1$ fewer node and $3$ fewer edges than $G_k$.  This also means, by induction, that $G_k$ has $k$ fewer nodes and $3k$ fewer edges than $G_0 = G$.
Now the key step you seem to be missing: take $\color{red}{k = \lfloor {n-1 \over 3} \rfloor}$.
The number of edges in $G_k = (2n-1) - 3 k = (2n-1) - 3 \lfloor {n-1 \over 3} \rfloor \ge (2n-1) - (n-1) = n.$
The number of nodes in $G_k = n - k = n - \lfloor {n-1 \over 3} \rfloor.$  Now $\lfloor {n-1 \over 3} \rfloor \ge {n-1 \over 3} - {2\over 3} = {n\over 3}-1$, so $n - \lfloor {n-1 \over 3} \rfloor \le n - ({n\over 3}-1) = {2\over 3}n+1$.
Therefore, $G_k$ has $\ge n$ edges and $\le {2\over 3}n + 1$ nodes.  This is basically what the question wants.  To be really precise, remove more edges until we have exactly $n$ edges, and this new $G'$ still has the same node-set $V'$ as $G_k$, and so  $|V'| \le {2\over 3}n + 1$.  Some of these nodes may have no edges (i.e. they are isolated), so the union of the edges $\subseteq V'$, i.e., the union of edges may have even fewer nodes, which is not a problem.
