# Minimum degree of a graph at least $\frac{1}{2}(n-1)$ implies connectedness

A few days ago I began a foray into graph theory on a whim, using a discrete mathematics book that I picked up a while ago. I'd like a HINT for this problem, if someone would be so inclined as to provide me with one.

Let $G$ be a graph of order $n$. Prove that if $\delta(G) \ge \frac{1}{2}(n-1)$, then $G$ is connected.

Here $\delta(G)$ is the minimum degree of $G$. In a previous problem I obtained a sharp bound of $\frac{1}{2}(p-1)(p-2)$ for the size of a disconnected graph. I wanted to take $\frac{1}{4}n(n-1)$ as the minimum number of edges of $G$ ($\frac{1}{2}(n-1)$ per vertex times $n$ vertices times $\frac{1}{2}$ to account for sharing) and take (using $q$ as the size of $G$) $q \ge \frac{1}{4}n(n-1) \ge \frac{1}{2}(n-1)(n-2)$, then use induction to show that the last inequality held true, forcing $q$ above the upper bound for a disconnected graph.

It would have been very nice if this had actually worked. Unfortunately, I didn't test the inequality very far, and it fails to hold already at $n=5$.

Any hints (not answers!) are most appreciated. Thanks!

-
Given two vertices $x,y$, show they have a common neighbor. –  Gerry Myerson Nov 22 '12 at 5:40
@GerryMyerson not quite true - only if there is no edge between the two –  Thomas Andrews Nov 22 '12 at 16:47
@Thomas, yes, quite right. –  Gerry Myerson Nov 22 '12 at 22:25

## 3 Answers

Assume there are at least $2$ connected components. Then there is a vertex in each component that has degree at least $\frac{1}{2}(n-1)$. What does that imply about the number of vertices in each component, and thus the total number of vertices in the graph?

-
Since there's a vertex in each component with degree at least $\frac{1}{2}(n-1)$, the order of each component is at least $\frac{1}{2}(n-1)+1$. Even for 2 components, this yields a total of $\frac{1}{2}(n-1)+1 + \frac{1}{2}(n-1)+1 = n-1+2=n+1$ vertices, contradicting the assumption that $|V(G)|=n$. This works, right? –  Alex Petzke Nov 22 '12 at 15:54
Yes, that's it. –  Michael Biro Nov 23 '12 at 1:27
Good. Thanks for the help. –  Alex Petzke Nov 23 '12 at 3:42

Suppose to the contrary that there are $2$ or more components.

If $n$ is even, say $n=2k$, some component has $\le k$ vertices.

If $n$ is odd, say $n=2k+1$, some component has at most $k$ vertices.

-

Not only is the graph connected, its diameter is at most $2$.

-