Graph Theory: Prove that G must be connected Let $G$ be a simple graph with $n$ vertices and $ \frac 1 2 (n-1)(n-2)+1$ edges. Prove that $G$ must be connected.
Thank you!

[Edited - thanks to M. Vinay who spotted the initial mistake!]
Suppose for contradiction that the graph is disconnected. Then it is possible to partition the graph into two subgraphs (disconnected from one another), with $k$ vertices and $n- k$ vertices respectively.
By a simple counting argument, you should be able to show that these two subgraphs can have at most $\frac 1 2 k(k-1)$ and $\frac 1 2 (n-k)(n-k-1)$ edges respectively.
It then remains to check that, for any value of $k$ between $1$ and $n-1$,
$$ \frac 1 2 k(k-1) + \frac 1 2 (n-k)(n-k-1) < \frac 1 2 (n-1)(n-2) + 1,$$ 
which would give a contradiction.
