Connected Graph

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

• 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$? Commented May 4, 2010 at 19:31
• Yes Robin you are correct. Commented May 4, 2010 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$.
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$.
• Nitpick. If $w$ does not exist, then G is clearly connected, so there is no need to apply induction. Commented May 4, 2010 at 19:58