LetGbe a graph withn≥ 2 vertices. Prove that if δ(G) ≥ (1/2)n, thenGis connected.

Printable View

- December 8th 2009, 01:09 PMdynas7yGraph Theory - Connection
Let

*G*be a graph with*n*≥ 2 vertices. Prove that if δ(*G*) ≥ (1/2)*n*, then*G*is connected. - December 9th 2009, 08:51 PMemakarov
Could you remind what δ(

*G*) is? - December 10th 2009, 04:29 AMdynas7y
δ(

*G*) is the minimum degree of a vertex in G. - December 10th 2009, 07:01 AMemakarov
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. - December 10th 2009, 09:23 AMdynas7y
Loops are not permitted.

- December 10th 2009, 10:39 AMemakarov
I hope that this solves the problem then.