# Thread: Graph Theory - Connection

1. ## Graph Theory - Connection

Let G be a graph with n ≥ 2 vertices. Prove that if δ(G) ≥ (1/2)n, then G is connected.

2. Could you remind what δ(G) is?

3. δ(G) is the minimum degree of a vertex in G.

4. 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.

5. Loops are not permitted.

6. I hope that this solves the problem then.