Proof - Graph Connectedness

Question

Let $n\ge2$ be an integer. Let $G$ be a graph with $n+1$ vertices and more than ${n \choose 2}$ edges. Show that $G$ is connected.

Here's my attempted solution to the above problem:

Induction on $n$:

Base case: $n=2$

So $n+1=3$ vertices. $\vert E\vert \gt {2 \choose 2} = 2$ so at least 3 edges, so connected.

Inductive step:

Assume $G$ connected for graph with $n+1$ vertices and $\vert E\vert \gt {n \choose 2}$ for all $n\ge2$.

Define $G\prime$ graph with $n+2$ vertices and $\vert E\vert \gt {n+1 \choose 2}$. Notice that $G\prime$ forms the complete graph $K_{n+1}$ with $n+1$ vertices and exactly ${n+1 \choose 2}$ edges (which is connected by IA). Now assume for contradiction that $G\prime$ is disconnected.

Since we need to use more edges than ${n+1 \choose 2}$ that are used for $K_{n+1}$, there is nowhere to else to add the edge back in other than between the complete graph and the vertex not included in it. We then obtain one connected component or a connected graph $G\prime$ which contradicts initial assumption. All graphs $G$ connected for $n\ge2$. (Q.E.D)

Is this proof correct?

Any tips, corrections, help would be greatly appreciated.

EDIT:

Removed use of removed vertex in proof. Instead, I rely solely on complete graph.

Answer 1

Here's a non-inductive proof. Suppose the graph is disconnected. That means that there exist 2 smaller disconnected from each other graphs of size $k$ and $l$, with $k+l = n+1$, and $l \ge 1$, $k \ge 1$. Let's then count the max number of edges we can have. Assume the two subgraphs are fully connected, then number of edges is:

$$\frac{k(k-1)}{2} + \frac{l(l-1)}{2} = \frac{n(n-1)}{2} - (k-1)(l-1) \le \frac{n(n-1)}{2}$$

Thus the graph has to be connected.

Answer 2

I am not seeing why $G''$ necessarily forms the complete graph on $n+1$ vertices.

This is how I would try it. Let $m$ be precisely the size of the largest connected component of $G$ [where $G$ is defined to be the graph on $n+1$ vertices with more than ${n \choose 2}$ edges].

If $m=n$ then $G$ can have at most ${n \choose 2}$ vertices [make sure you see why]. If $m \le n-1$ then use the fact that every vertex in $G$ can have degree at most $m-1$ [make sure you see this], so as $m$ satisfies $m \le n-1$ it follows that every vertex in $G$ can have degree at most $n-2$. So by the Handshaking Lemma there can be at most $\frac{(n-2)(n+1)}{2} \le {n \choose 2}$ [simple algebra to check]. Both of which contradict that $G$ has more than ${n \choose 2}$ edges.