How to prove this graph is connected?

Question

If I have a simple graph G with p vertices $\geq 3$ and with a number of edges > $\frac{(p - 1) \cdot (p - 2)}{2}$, how can I prove it is connected?

Answer 1

A not connected graph has at least two connected components. Moreover, a graph with $n$ vertices has at most $\frac{n(n-1)}2$ edges (and then it's the complete graph). Therefore, if $\mathbf{G}$ has two components, then it has at most $$\max_{1\leq n\leq p-1}\left(\frac{n(n-1)}2+\frac{(p-n)(p-n-1)}2\right)$$ edges. We can calculate that this value is equal to $\frac{(p-1)(p-2)}2$ (i.e. that it is maximized by $n=1$ and $n=p-1$).

Now we can proceed by contradiction: if $\mathbf{G}$ were not connected, then it would have less than $\frac{(p-1)(p-2)}2$ edges, which contradicts the hypothesis. Therefore it is connected.