6
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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$? $\endgroup$ – Robin Chapman May 4 '10 at 19:31
  • $\begingroup$ Yes Robin you are correct. $\endgroup$ – Oscar Leroy May 4 '10 at 19:33
11
$\begingroup$

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

$\endgroup$
  • 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$ – François G. Dorais May 4 '10 at 20:14
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nitpick. If $w$ does not exist, then G is clearly connected, so there is no need to apply induction. $\endgroup$ – Tony Huynh May 4 '10 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.