Suppose $\Delta(G) + \delta(G) \geq n-1$. Can we conclude that $G$ is connected?
$\begingroup$
$\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$– Robin ChapmanCommented May 4, 2010 at 19:31
-
$\begingroup$ Yes Robin you are correct. $\endgroup$– Oscar LeroyCommented May 4, 2010 at 19:33
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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$.
answered May 4, 2010 at 20:03
-
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
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
Take a vertex $v$ of maximum degree, then delete a vertex $w$ not adjacent to $v$.
answered May 4, 2010 at 19:34
-
$\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