Question: 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](https://imomath.com/srb/zadaci/2016_smo_booklet.pdf) (page 10, problem 5) and it is a kind of not natural to me. Can someone try to walk another way?

Answer: 
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](https://en.wikipedia.org/wiki/Handshaking_lemma) 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$.
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.