6
$\begingroup$

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!

  • 0
    @Thomas, yes, quite right.2012-11-22

4 Answers 4

8

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?

  • 0
    Good. Thanks for the help.2012-11-23
3

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

2

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.

0

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