Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$

Question

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$

This is what I got

let $u \in V(G)$, since $G$ have three components, there are at least 2 vertices of $G$ that are not adjacent to $u$, so $deg(u) \leq (n-3)$ in $G$. How can I connect this to $\overline G$?

Answer 1

I'm assuming that $\Delta$ is the maximum degree, and $\bar{G}$ is the complementary graph.

If $G$ has three connected components, then the (or one of the) smallest one has cardinality less or equal to $n/3$, so the sum of the number of nodes in the other two is $2n/3$ or greater.

That means that exists a node in the smallest component connected to at least $2n/3$ other nodes in $\bar{G}$, so $\Delta(\bar{G})\ge2n/3$. This holds for $n \ge 3$

In general, if you have $k$ connected components, then $\Delta(\bar{G})\ge(k-1)n/k$, with $n\ge k$