If $G$ and $\overline G$ are both $r$-regular then $G$ has odd order.

Question

Show that if $G$ and $\overline G$ are both $r$-regular for some nonnegative integer $r$, then $G$ has odd order.

$\hskip 2 in$

Is this a counterexample? If not, why?

Answer 1

Clearly (a) and (b) are not complementary. Also, if $|V(G)|=k$ and $G$ is $r$-regular, then $\bar{G}$ is $(k-1-r)$-regular and $r=k-1-r$ or $k=2r+1$.