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.
Prove that complement of graph is Eulerian
eulerian-pathgraph theory
Best Answer
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.