# Complement of a connected graph

What are the conditions for the complement of a connected graph to be connected?

In particular, when is the complement of a connected regular graph connected? I feel that if the regularity of graph is $\left\lceil\frac{n-1}{2}\right\rceil$, its complement should be connected, though it's mere intuition.

• Do you think that such conditions exist? Please: be more specific with your question. There could exist too many possible good answers, but maybe you have something precise in your mind. – Crostul May 30 '15 at 12:40
• @ Crostul, edited! – Sry May 30 '15 at 12:54
• I think $K_{m,m}$ (for $m\ge 1$) is a counterexample to the particular conjecture you gave in the question; its complement is two disjoint copies of $K_m$, right? – user21467 May 30 '15 at 13:39
• (The extremality of that situation suggests a counting argument: if the graph is $k$-regular with $k < \lceil\frac{n-1}{2}\rceil$, the complement will have too many edges to be disconnected. I doubt this is an interesting enough condition for you, though.) – user21467 May 30 '15 at 13:42
• @Steven Taschuk, you are right. Thanks for pointing. – Sry Jun 1 '15 at 11:27

## 1 Answer

"For every two partitions of the vertices on two groups there must be missing edge between groups."

$=>$ if there are $\ge 2$ connected components in the complement graph then we can group our vertices into two groups: {one connected component, the others}. For the initial graph there is no missing edge between them.

$<=$ if complement graph is connected, than for every partition there is an edge between groups. And this edge is missing for the same pertition in the initial graph.

Proved.

• sorry I didn't understand what the second paragraph concludes? – Sry May 30 '15 at 13:06
• that the connectivity of the complement graph provides holding mentioned condition for the initial graph. – Andrei Kulunchakov May 30 '15 at 13:17
• we assume complement to be disconnected with mentioned condition,but where is a contradiction to lead us to the connectivity of complement. – Sry May 30 '15 at 13:29
• What does "two groups" mean please? What's the conclusion of your derivation? – PSPACEhard May 30 '15 at 13:40