0
$\begingroup$

Let G be a graph with $n$ vertices such that $n\geq2$. Prove that, if $\mathrm{deg}(v)\geq \frac{n-2}{3}$ for every vertex $v$ in G, then G contains at most two connected components.

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. May 26 '18 at 18:45
1
$\begingroup$

Assume there are are at least 3 connected components. Then there must be a connected component of size $\le\frac{n}{3}$. Let $v$ be a vertex in that connected component. By assumption we have $deg(v)\ge\frac{n-2}{3}$. Since the size of that connected component is at most $\frac{n}{3}$ than it must be that $deg(v)\le\frac{n}{3}-1=\frac{n-3}{3}$. So we get both $deg(v)\ge\frac{n-2}{3}$ and $deg(v)\le\frac{n-3}{3}$, a contradiction. Thus, there must be at most 2 connected components.

$\endgroup$

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.