Let G be a simple graph of order $n\geq 2$. If $|E(G)|>\binom{n-1}{2}$,then G is connected. Let G be a simple graph of order $n\geq 2$. If $|E(G)|>\binom{n-1}{2}$,then G is connected.
One of the solution I get is as shown as below:
Suppose G is not connected,
Then G is a disjoint union of two graphs $G=G_1 \cup G_2$ where $G_1$ has $x$ vertices and $G_2$ has $n-x$ vertices.
Counting the number of edges in G with respect to $G_1$ and $G_2$ we see
$$|E(G)|=|E{G_1)|+|E(G_2}|\leq \binom{x}{2}+\binom{n-x}{2}\leq \binom{n-1}{2}$$
This is a contradiction.
I wonder how to get the inequality $$\binom{x}{2}+\binom{n-x}{2}\leq \binom{n-1}{2}$$
Or is there any easier way to prove it?
 A: This is the right way to do it.
The inequality is actually not complicated. We get
$$\frac{x(x-1)}{2}+\frac{(n-x)(n-x-1)}{2}=\frac{(n-x)^2-(n-x)+x^2-x}{2}=\frac{n^2-2nx+x^2-n+x+x^2-x}{2}=\frac{n^2-2nx-n+2x^2-x}{2}\leq\frac{n^2-3n+2}{2}$$
We thus need to show that
$$-2nx-n+2x^2-x\leq -3n+2$$
Equivalently
$$-2(n-x)x\leq -2n+x+2$$
or
$$-2n-2x\leq -2(n/x)+1+2/x$$
If $x=1$ this can be checked directly, and if $x\geq 2$ we have
$$-2n-2x\leq -2n-2\leq -n+1\leq -2(n/x)+1+2/x$$
A: Note that $\binom{n-1}{2}=\binom{n}{2}-(n-1)$ and that $K_{n}$ is $n-1$-edge connected... meaning that in order to disconnect $K_{n}$ by deleting edges you must delete at least $n-1$ of them.  Then since $|G|>\binom{n-1}{2}=\binom{n}{2}-(n-1)$ it follows that fewer than $n-1$ edges were deleted from $K_{n}$ to obtain $G$ and hence $G$ is connected.
EDIT: An even better solution (not assuming anything about the connectivity of $K_{n}$ is the following.
If $|G|>\binom{n-1}{2}$ then look at what the average degree of your vertices is.  $$\frac{1}{n}\sum \text{deg}(v)=\frac{2}{n}|E|>\frac{2}{n}\binom{n-1}{2}=\frac{(n-1)(n-2)}{n}=n-3+\frac{2}{n}.$$
Thus there is a vertex $v$ with degree at least $n-2$.  So there is a connected component of $G$ containing $v$ and all its neighbors with size at least $n-1$; thus there is at most 1 vertex not adjacent to $v$, call that vertex $u$.  If $u$ is an isolated vertex, then you are missing at least $n-1$ edges (since $u$ is adjacent to none of the other $n-1$ vertices).  But, $\binom{n}{2}-(n-1)=\binom{n-1}{2}$ so $u$ cannot be an isolated vertex, hence it is adjacent to one of the neighbors of $v$; hence the graph is connected.
You could simplify a little by proving first that there are no isolated vertices (vertices of degree $0$).  Then you immediately have that $u$ must be adjacent to a neighbor of $v$.
