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

4$\begingroup$ I presume $n$ is the number of vertices, and $\Delta(G)$ and $\delta(G)$ are respectively the maximum and minimum vertexdegrees of the graph $G$? $\endgroup$– Robin ChapmanCommented May 4, 2010 at 19:31

$\begingroup$ Yes Robin you are correct. $\endgroup$– Oscar LeroyCommented May 4, 2010 at 19:33
3 Answers
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 $a1$ (resp. $b1$), we see that $\Delta(G) \leq a1$ and $\delta(G) \leq b1$. So $\Delta(G) + \delta(G) \leq a+b2 = n2$.

2$\begingroup$ 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. $\endgroup$ Commented May 4, 2010 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.
Take a vertex $v$ of maximum degree, then delete a vertex $w$ not adjacent to $v$.

$\begingroup$ Nitpick. If $w$ does not exist, then G is clearly connected, so there is no need to apply induction. $\endgroup$ Commented May 4, 2010 at 19:58