Given a graph $G$ on $n$ vertices, with $\delta(G) \ge \frac{n-1}{2}$, show that $G$ is connected

Question

Given a graph $G$ on $n$ vertices, with $\delta(G) \ge \frac{n-1}{2}$, show that $G$ is connected.

I believe I need to prove this via contradiction by first assuming G is not connected? I'm not sure where to go from there. Any help is appreciated.

Answer 1

Hint: If $G$ is not connected, what is the maximal possible degree of a vertex in the smallest connected component?

Answer 2

Suppose that we have two points $A$ and $B$ which are not connected. And let $M$ and $N$ be the sets of the neighbors of $A$ respectively $B$. Then since $A$ and $B$ are not connected we have $A\notin N$ and $B\notin M$. Suppose they don't have common neighbor, so $M\cap N =\emptyset $. Now by PIE we have $$n-2\geq|M\cup N|=|M|+|N|-|M\cap N| \geq 2{n-1\over 2}$$ A contradiction.

Answer 3

Assume the statement is false. Then there are at least 2 connected components of $G$. Notice that in each component there will be a vertex $v$ with the property that $d(v)\geq \frac{(n-1)}{2}$. Hence each of these connected components must have at least $1+\frac{(n-1)}{2}$ vertices (remembering to include $v$) and so over all components there are at least $2\left[1+\frac{(n-1)}{2}\right]=n+1$ vertices of $G$, a contradiction.