Proving that a graph is connected?

Question

I'm trying to prove that this graph is connected given the provided information.

Let $G$ be a simple undirected graph with $n \geq 2$ vertices. Prove that if $δ(G) \geq \frac{n}{2}$, then $G$ is connected.

I can see from testing a few examples that it's definitely true. As for the actual proof, I'm stuck:

If we have $n$ vertices, then we have at most $\frac{n(n-1)}{2}$ edges. However, I'm still not seeing what the minimum vertex degree has to do with the number of edges at any other vertices, and especially in showing that we have enough edges to guarantee connectedness.

I don't feel like I'm approaching this problem the right way. If anyone could help, that would be much appreciated.

Answer 1

By contradiction: suppose the graph is not connected, then it has at the very least $2$ connected components, so the size of the smallest component is at most $\frac{n}{2}$ Meaning the degree of a vertex in that component is at most $\frac{n}{2}-1$ meaning the minimum degree is at most $\frac{n}{2}-1$. Thus a graph with minimum degree at least $\frac{n}{2}$ must be connected.

Answer 2

HINT: Let $u$ and $v$ be any two vertices. Let $N(u)$ be the vertex $u$ together with its neighbors, and define $N(v)$ similarly. Is it possible that $N(u)\cap N(v)=\varnothing$?