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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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. $\endgroup$– Brian MoehringMay 16, 2021 at 17:44
-
$\begingroup$ [I'm ignoring $n=1$ in my above comment, so if you do decide to prove the claim, assume $n > 1$] $\endgroup$– Brian MoehringMay 16, 2021 at 17:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered May 16, 2021 at 17:07