How to better prove this statement? Let G be a graph with $n$ vertices and $k > {n-1 \choose 2}$ edges. Then G is connected I tried doing it by contrapositive. I'm here to ask two things
1) Whether this proof is correct
2) If there's a better, more direct way of proving this using graph theory
Here's how I did it:
Let G be a non-connected graph with n vertices. Then G has at most ${n-1 \choose 2}$ edges
Proof: 
If G isn't connected, it has two subgraph components F and H, such that $ \#V_F = m$ and $\#V_H = n - m$, $ 1 \le m \le n-1$
$\#E_F + \#E_H = \#E_G$ and also $\#E_F \le \#E_{K_m}$ and $\#E_H \le \#E_{K_{n-m}}$
So from this follows that $ \#E_G = \#E_F + \#E_H \le \#E_{K_m} + \#E_{K_{n-m}} = {m \choose 2 } + {n-m \choose 2}$ 
So I'll define $f(m) = {m \choose 2 } + {n-m \choose 2}$ and I want to prove that 
$ \Delta f(m) \le 0$, for $1 \le m \le \lfloor \frac {n-1}{2} \rfloor$
$\Delta f(m) \ge 0$, for $\lceil \frac{n-1}{2} \rceil \le m \le n-1$
$f(m) = f(n-1) = {n-1 \choose 2}$
This would prove f(m) has its maximum value at m=1. And then the maximum amount of edges in G is f(1).
I'm not writing the proof for these three last statements, but it's easy to prove knowing that $\Delta f(m) = 2m+1-n$
Thanks in advance!
 A: Your proof is correct, but there is a simple one using the degree sum formula. 
Since twice the number of edges is the sum of the vertex degrees, the average degree is greater than $$\frac{(n-1)(n-2)}{n} > n-3$$
so there must be a vertex $v$ of degree at least $n-2$.  If $v$ is of degree $n-1$ the graph is clearly connected, so suppose $v$ is of degree $n-2$, and let $x$ be the one vertex not adjacent to $v$.  The subgraph induced by $v$ and its neighbors has at most $\binom{n-1}{2}$ edges, so there is an edge from $x$ to some neighbor of $v$, and the graph is connected.  
A: This proof is correct, and I think most if not all other proofs are variants of this one. (Edit: saulspatz gives a proof very different from this one, which I like, so clearly that was false. I mean, not literally false, since I gave myself an out by not making an absolute statement, but maybe I was overstating my case.)
There are a couple of other, very similar ways to get to where you're going:


*

*Since $f(m)$ is a convex function, it is maximized over the interval $[1,n-1]$ at one of the boundary points: $f(1)$ or $f(n-1)$. In this case, the two are equal, and both give $\binom{n-1}{2}$.

*Alternatively, we can minimize the quantity $\binom n2 - f(m) = m(n-m)$. This has a combinatorial interpretation as well: it is the number of edges guaranteed to be missing from a graph with a connected component of size $m$.

*Either way, instead of thinking about the discrete derivative $\Delta f(m)$, it's fine to just deal with the derivative $f'(m) = 2m-n$. This leads to a proof that $m=1$ and $m=n-1$ are not just better than all integer values $m \in \{2,3,\dots,n-2\}$ but also fractional values like $m=1.5$, but that's fine as long as we don't end up getting a fractional optimal value.


We could also put together two well-known facts: first, that if a graph is not connected, then its complement is; second, that a connected graph on $n$ vertices has at least $n-1$ edges. This lets us conclude that at least $n-1$ edges are missing from a disconnected graph, so it has at most $\binom n2 - (n-1) = \binom{n-1}{2}$ edges. But proving the first of these facts is strictly harder than proving the result we're trying to get, so this isn't really a shortcut.
A: Your proof is a valid one. As an another approach, by using the argument below, we can also go with induction:

Let $G$ be a non-connected graph with n vertices. Then $G$ has at most ${n-1 \choose 2}$ edges.

Since a graph with $1$ vertex is said to be connected, we should start from $n=2$. For $n = 2$, we can construct a disconnected graph in only one way where there are no edges, that is $\binom{2-1}{2} = 0$.
Now suppose, inductively, that the argument holds for all $n$. Then for a graph with $n+1$ vertices, if we construct this graph by adding a one vertex to a graph with $n$ vertices, in order to maximize the number of edges, obviously we should add the new vertex to the component with more vertices. Therefore, we add the new vertex to the component with $n-1$ vertices. Then connecting all other vertices to the new vertex (except the isolated vertex that provides disconnectivity), we add $n-1$ more edges to $\binom{n-1}{2}$ edges to get:
$$\binom{n-1}{2}+n-1 = \frac{(n-1)(n-2)}{2}+(n-1) = \frac{n^2-n}{2} = \frac{n(n-1)}{2} = \binom{n}{2}$$
Since it holds for $n+1$, by induction, the argument holds for all $n \ge 2$.
A: A slightly different approach. If we assume that a graph on $n$ vertices is not connected, it has at least two connected components and the number of its edges  is at most
$$ \max_{\substack{a+b=n\\ a,b\geq 1}}|E(K_a)|+|E(K_b)| = \max_{\substack{a+b=n\\ a,b\geq 1}}\binom{a}{2}+\binom{b}{2}=\max_{1\leq a \leq n-1}\frac{2a^2-2an-n+n^2}{2}$$
where $f(a)=2a^2-2an-n+n^2$ is a convex function. It follows that the previous maximum is attained at $a=1$ or at $a=n-1$ and a disconnected graph on $n$ vertices has at most $\binom{n-1}{2}$ edges.
