Proof of connectedness in a simple graph Let G be a simple graph with n vertices. Prove that if the degree of every vertex is at least $\frac{n-1}2$, then G is connected. I've tried the degree sum formula, but it doesn't seem to get me anywhere. Below is my attempt. $\sum_{v\in V}deg(v) \ge \frac{n(n-1)}2$ $|E| \ge \frac{n(n-1)}4$ ... There's something about the value $\frac{n-1}2$ that catches my attention. Intuitively it means that for every vertex $v \in V$, $v$ is connected to at least $half$ of the other $n-1$ vertices. But I don't know how to proceed from there.

Take two vertices $v_1 \
eq v_2$. I'll show they are in the same connected component of the graph.

If they are connected then $v_1$ and $v_2$ are in the same connected component and we are done. So assume henceforward that they're not connected. Then there are $n-2$ points of the graph left, and $d(v_1) \ge \frac{n-1}{2}$ of them are neighbours of $v_1$, and $d(v_2) \ge \frac{n-1}{2}$ are neighbours of $v_2$. If these sets of neighbours were disjoint, we'd have $2\frac{n-1}{2} = n-1$ many remaining points, contradiction.

So they have a common neighbour, and thus a path between $v_1$ and $v_2$ exists.