# 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$? – 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$.

-
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.

-

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. – Tony Huynh May 4 '10 at 19:58