0
$\begingroup$

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

Can someone please help me complete this proof. Thanks.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user460345 Jul 6 '17 at 21:08
  • $\begingroup$ 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... $\endgroup$ – Hamed Jul 6 '17 at 21:17
  • $\begingroup$ I see what's up now that you restated the problem. I was parsing it wrong the whole time. Thanks. Now it makes perfect sense. $\endgroup$ – user460345 Jul 6 '17 at 21:22
  • $\begingroup$ Sorry I forgot to accept your answer. I just did. Thanks, again. $\endgroup$ – user460345 Jul 6 '17 at 21: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.