So in this thread:
I just have one small question about @jdoerrie's answer. I understood everything except for his sentence:
Let $c_j$ be such that $|V(c_j)| \geq 4$ and $|E(c_j)| \geq 2\cdot|V(c_j)| - 3$. Such a $c_j$ must exist because $G$ could not have $2n-3$ edges otherwise.
I tried getting to the same conclusion but couldn't. It seems as though it's very simple and obvious. Can anyone enlighten me and explain formally why such a $c_j$ must exist?
Thanks!
On
If $c_j$ is a component with $3$ or fewer vertices, then $|E(c_j)|\le2\cdot|V(c_j)|-3$ for easy-to-see reasons. If the same inequality held for all components with $4$ or more vertices, then, by summing the inequalities over all $k$ components, we'd have
$$|E(G)|\le2\cdot|V(G)|-3k$$
which (because we're only concerned when $k\gt1$) is strictly less than $2\cdot|V(G)|-3$, in contradiction to the assumption of the problem.
Case 1: $|V|\le3$. Then no such component need exist; however this is excluded by the problem hypothesis.
Case 2: $|V|>3$ and $|V(c_j)|\le 3$ for all components $c_j$. Then $|E|\le |V|$, which contradicts $|E|\ge 2|V|-3$.
Case 3: $|V|>3$ and $|V(c_j)|\ge 4$ for at least one component $c_j$. Suppose $|E(c_j)|< 2|V(c_j)|-3$ for all such components with at least 4 vertices. But also $|E(c_j)|\le 2|V(c_j)|-3$ for all components with fewer than 3 vertices. Then, we sum over all components: $$|E|=|E(c_1)|+\cdots+|E(c_k)|< (2|V(c_1)|-3)+\cdots+(2|V(c_k)|-3)=2|V|-3k\le2|V|-3$$
Note that we have $<$ because at least one $\le$ is strict, since there is at least one component with 4+ vertices. The end result is $|E|<2|V|-3$, a contradiction.