# Show that in a graph with $n$ vertices, if $\delta + \Delta \ge n - 1$, then the graph must be connected.

$\Delta$ stands for the maximum degree in a graph and $\delta$ stands for the minimum degree in a graph.

Hint: First show that there must be some component that contains at least $\Delta + 1$ vertices. Then show that if there were any other component, these two components together would contain more than $n$ vertices.)

Using the hint I tried this below:

Let $G$ be a graph with maximum degree $\Delta$. Assume $G$ is disconnected. Suppose every component of $G$ has at most $\Delta$ vertices. Then every component has maximum degree $\le \Delta - 1.$ But $G$ must have maximum degree $\Delta.$ Contradiction. Now that we know there exist at least one component with $\Delta + 1 = n$ vertices we conclude we can't have have any more components because even the smallest component adds one vertex to the component with $n$ vertices.

I am having trouble fitting the hypothesis $(\delta + \Delta \ge n - 1)$ into the proof. I think $\Delta + 1 = n \implies \delta + \Delta \ge n - 1,$ but the converse is not true.

Let $G=(V,E)$ be a graph of maximum degree $\Delta$. Then there is a vertex $x$ which is connected to $\Delta$ other vertexes. This means $G$ contains a component of at least $\Delta+1$ vertexes. Let $H=(V',E')$ be this component of $G$.
Assume $G$ is not connected. Let $y\in V-V'$ be any vertex not in the component $H$. Let $d$ denote the degree of $y$. Note that $d\geq \delta$ by definition of $\delta$. Then since $y$ is connected to $d\geq \delta$ vertexes, the component it belongs to has order at least $\delta+1$. Therefore $G$ has order at least $\delta+1 + \Delta+1\geq n+1$, a contradiction.
• Thank you. Your proof makes perfect sense. I am having difficulty seeing why this means $\Delta + \delta \ge n - 1$ implies disconnectedness. In other words, why don't we start the proof with "Assume the hypothesis holds". Are we doing it implicitly? – user460345 Jul 6 '17 at 21:08
• I'm confused by what you wrote! The statement you want to prove is: "Let $G$ be a graph of order $n$ in which $\Delta+\delta\geq n-1$. Prove that $G$ is connected." Why would you say "$\Delta+\delta\geq n-1$ implies disconnectedness?" it doesn't... – Hamed Jul 6 '17 at 21:17