Let G be a graph with n ≥ 2 vertices. Prove that if δ(G) ≥ (1/2)n, then G is connected.
I think that under this condition not only G is connected, but every 2 vertices have a path between them of length at most 2.
Let V be the set of vertices. Take any 2 distinct vertices a and b. If they are connected by an edge, fine. Suppose there is no direct edge. Let U=V-{a,b}; then |U| = n-2. Now, a is connected with at least n/2 vertices. If a does not have a loop, then all those n-2 vertices are in U. Similar thing holds for b. So, those two subsets of U must intersect.
Please let me know if loops are permitted in this problem.