Undirected Graph Proof for Connection

Question

If I have an undirected graph $G = (V, E)$, where $n = |V|$, and $n$ is even, how can I prove that for all $n \ge 2$ and every $v \in V$ has degree $(v) \ge \frac{n}{2}$, $G$ is necessarily connected.

Any help is appreciated.

Answer 1

Assume $G$ is not connected, i.e. it can be partitioned into two smaller graphs $G_1, G_2$ with $n_1>0$ and $n_2>0$ vertices, respectively, such that $n_1+n_2=n$. The degree of any vertex in $G_1$ is $\le n_1-1$. Since $G_1$ does indeed have at least one vertex, we need $n_1-1\ge \frac n2$. Similarly, $n_2-1\ge \frac n2$, hence we obtain the contradiction $n=n_1+n_2\ge \frac n2+1+\frac n2+1=n+2$.

Note: The proof does not require that $n$ is even and would also work with $\operatorname{deg}(v)\ge \frac{n-1}2$ instead of $\operatorname{deg}(v)\ge \frac{n}2$.