Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose $\Delta(G) + \delta(G) \geq n-1$. Can we conclude that $G$ is connected?

share|improve this question
4  
I presume $n$ is the number of vertices, and $\Delta(G)$ and $\delta(G)$ are respectively the maximum and minimum vertex-degrees of the graph $G$? –  Robin Chapman May 4 '10 at 19:31
    
Yes Robin you are correct. –  Oscar Leroy May 4 '10 at 19:33

3 Answers 3

Take a vertex $v$ of maximum degree, then delete a vertex $w$ not adjacent to $v$.

share|improve this answer
    
Nitpick. If $w$ does not exist, then G is clearly connected, so there is no need to apply induction. –  Tony Huynh May 4 '10 at 19:58

Yes. Suppose that $V(G)$ can be split into two sets $A$ and $B$ of respective sizes $a \geq b \geq 1$, and no edges between the two sets. Since vertices in $A$ (resp. $B$) have degree at most $a-1$ (resp. $b-1$), we see that $\Delta(G) \leq a-1$ and $\delta(G) \leq b-1$. So $\Delta(G) + \delta(G) \leq a+b-2 = n-2$.

share|improve this answer
2  
It's really nice to see three completely different solutions. I really like JBL's solution since it gives much more positive information. Mine shows in addition that the result is optimal. –  François G. Dorais May 4 '10 at 20:14

We can do this without inducting on the size of the graph: choose a vertex $v$ of degree $\Delta$ and any other vertex $w$ of degree $d \geq n - 1 - \Delta$. Either $w$ is adjacent to $v$ or, by the pigeonhole principle, they have a common neighbor among the other $n - 2$ vertices. So not only is the graph connected but it's actually of diameter at most 4.

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.