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.
Best Answer
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$?