Proof of connectedness in a simple graph

Question

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.

Answer 1

Take two vertices $v_1 \neq 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.

Answer 2

Let $v \neq w$ be two vertices. I show that $v,w$ are connected by a path with at most 2 edges.

In fact, consider $Adj(v) = \{ u : (u,v) \mbox{ is an edge} \}$, and $Adj(w) = \{ u : (u,w) \mbox{ is an edge} \}$. If $v \in Adj(w)$ or $w \in Adj(v)$, then we are done.

Otherwise, $v \notin Adj(w)$ and $w \notin Adj(v)$. Since the graph is simple, we have $v \notin Adj(v)$ and $w \notin Adj(w)$, so $Adj(v) \cup Adj(w) \subseteq G \setminus \{ v,w \}$. But now

$$|Adj(v)|+|Adj(w)| \geq \frac{n-1}{2} + \frac{n-1}{2} = n-1 > |G \setminus \{ v,w \}| $$

Hence these two sets have nonempty intersection. Let $u \in Adj(v) \cap Adj(w)$. Then the path $(v,u), (u,w)$ connects the two vertices.

In particular this shows that $G$ is a connected graph.