Prove that, if $\deg(v)\geq \frac{n-2}{3}$ for every vertex $n$ in $G$, then $G$ contains at most two connected components

182 Views Asked by At

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

1

There are 1 best solutions below

1
On

Assume you can find vertices $u,v,w$ in three distinct components. Together, they have at least $n-2$ neighbours, but there are only $n-3$ other vertices ...