----------------SOMETHING WRONG WITH THIS PROOF. I AM TRYING TO FIX IT------------------------
Apart from the above illustrative proofs, an inductive proof exists too.
Let G be a disconnected graph with n vertices, where n >= 2.
The complement of G is a graph G' with the same vertex set as G,
and with an edge e if and only if e is not an edge of G.
Base case: We know that this is true for n = 2.
Assume that this is true for n <= k, where k is any positive integer.
Let this graph be G(k). The complement G'(k) is connected.
Let's look at the extra vertex in G(k+1) - call it X. The vertex X is connected to d vertices, where 0<=d<=k+1.
It cannot be connected to k vertices, because then then graph would
be connected. In the complement of the graph, X is connected to k-d
vertices. X must be connected to at least one other vertex because
1<=k-d<=k. Since the complement of G(k) is connected and X is
connected to at least a vertex in G'(k), then the graph G'(k+1) is also
By the inductive hypothesis, this is true for all n that are positive