MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

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|cite|improve this answer
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|cite|improve this answer

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

share|cite|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

Your Answer


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.