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
    Given two vertices $x,y$, show they have a common neighbor.2012-11-22
  • 0
    @GerryMyerson not quite true - only if there is no edge between the two2012-11-22
  • 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?

  • 4
    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?2012-11-22
  • 0
    Yes, that's it.2012-11-23
  • 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