1
$\begingroup$

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.

$\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$ Commented May 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$ Commented May 16, 2021 at 17:58

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .