# Prove that complement of graph is Eulerian

I have to prove that complement of Eulerian graph with odd number of vertices and with maximum degree of vertex $$\le \frac{n}{2}$$ where $$n$$ is number of vertices, is also Eulerian. I proved that every vertex in complement is even degree without using fact that maximum degree is $$\le \frac{n}{2}$$. But not sure how to prove that complement is connected? I thought to prove that G is self-complementar graph, but not sure how. Every help is appriciated.

• Note that if you are working with loopless graphs, self-complementary plus the assumptions in your problem implies $G$ is a cycle with $n=5$ vertices (prove this). If you extend "complements" to graphs with loops (not standard) then there are no self-complementary graphs with odd $n$. In either case, we note it's impossible to prove $G$ is self-complementary from the information given in the problem. Commented May 16, 2021 at 17:44
• [I'm ignoring $n=1$ in my above comment, so if you do decide to prove the claim, assume $n > 1$] Commented May 16, 2021 at 17:58

Suppose $$\overline G$$ is disconnected. Then since $$n$$ is odd, we can always find a partition of its components into two sides such that one side has at most $$\frac{n-1}2$$ vertices. Any vertex on this side is therefore connected to at least $$\frac{n+1}2$$ vertices (on the other side) in $$G$$, causing $$\Delta(G)>\frac n2$$, contradicting the initial assumption.