Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 3

up vote 3 down vote accepted

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?

share|improve this answer
3  
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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.