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