6
$\begingroup$

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

$\endgroup$
2
  • 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$ May 4, 2010 at 19:31
  • $\begingroup$ Yes Robin you are correct. $\endgroup$ May 4, 2010 at 19:33

3 Answers 3

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$
1
  • 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$ May 4, 2010 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$
1
  • $\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, 2010 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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