I'm trying to prove this by contradiction.
So, I'm assuming that the graph is not connected. But even if the graph is not connected, I believe it will still have n/2 degree vertices. I'm finding it hard to prove it this way.
Let G be a graph with n vertices where every vertex has a degree of at least n/2. Prove that G is connected.
graph theory
Related Question
- [Math] Let $G$ be a simple graph with n vertices where every vertex has degree at least $n/2$. Prove that $G$ is connected.
- [Math] Let G be a simple connected planar graph with at least three vertices. Prove that if every face of G has degree 3, then G has an even number of faces
- [Math] Prove that a connected simple graph where every vertex has a degree of 2 is a cycle (cyclic) graph
Best Answer
Assume a graph $G$ with the mentioned property is not connected. Hence it can be split into (at least) 2 connected components, call it $G_1$ and $G_2$. Both these sub-graphs must satisfy the property of each vertex having degree $n/2$ at least, and since there are no edges between vertices of $G_1$ and $G_2$, the number of vertices in both $G_1$ and $G_2$ must be at least $n/2$ to match the requirement.
Now observe that if $n=2k+1$ then at least $n/2$ means that both $G_1$ and $G_2$ must have at least $k+1$ vertices but that totals to $2k+2 = n+1$ for $G$ which is a contradiction. Similarly for $n=2k$ both $G_1$ and $G_2$ must each have at least $k + 1 $ vertices in order for each vertex to have degree at least $k$. Thus the total number of vertices in $G$ becomes $k+1 + k+1 = n+2$ which is a contradiction.