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!
$\endgroup$ 34 Answers
$\begingroup$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?
$\endgroup$ 3 $\begingroup$Not only is the graph connected, its diameter is at most $2$.
$\endgroup$ 0 $\begingroup$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.
$\endgroup$ $\begingroup$What happens with a graph with loops?
For example one with adjacent matrix: $$\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}$$
That has $$ \delta(G) = 2 > {(n-1)\over2} = {1\over2} $$ but is not connected
$\endgroup$
