# Graph Theory - Connection

• Dec 8th 2009, 02:09 PM
dynas7y
Graph Theory - Connection
Let G be a graph with n ≥ 2 vertices. Prove that if δ(G) ≥ (1/2)n, then G is connected.
• Dec 9th 2009, 09:51 PM
emakarov
Could you remind what δ(G) is?
• Dec 10th 2009, 05:29 AM
dynas7y
δ(G) is the minimum degree of a vertex in G.
• Dec 10th 2009, 08:01 AM
emakarov
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.
• Dec 10th 2009, 10:23 AM
dynas7y
Loops are not permitted.
• Dec 10th 2009, 11:39 AM
emakarov
I hope that this solves the problem then.