Find a graph $G$ on $7$ vertices such that both $G$ and $\overline G$ contain Eulerian circuits. $\bar G$ means complementary graph.
Graph is called Eulerian circuit if the trail is closed.
Please help me to find the reference about this problem, may be someone can give a hint.
Best Answer
Hint $$\deg_G(v)+\deg_{\bar{G}}(v)=6$$
You want both of them to be even, so you know exactly what the degrees should be. And you should be looking for $G$ so that both $G$ and $\bar{G}$ are connected.
Hint 2 If every vertex of $\bar{G}$ has degree $\geq \frac{7-1}{2}$ then $\bar{G}$ is automatically connected.