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.

  • $\begingroup$ 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. $\endgroup$ – Crostul May 30 '15 at 12:40
  • $\begingroup$ @ Crostul, edited! $\endgroup$ – Sry May 30 '15 at 12:54
  • $\begingroup$ 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? $\endgroup$ – user21467 May 30 '15 at 13:39
  • $\begingroup$ (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.) $\endgroup$ – user21467 May 30 '15 at 13:42
  • $\begingroup$ @Steven Taschuk, you are right. Thanks for pointing. $\endgroup$ – Sry Jun 1 '15 at 11:27

"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.


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

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.