# An Eulerian graph, even vertices, an Eulerian complement?

(task) a graph G conditions:

1. Eulerian Graph
2. even number of vertices
3. complement has an Euler circut

Is it possible or not ? If you think that it's possible, draw it, otherwise explain why not.

I'm not sure about the answer, but I was trying to draw it and I think that it isn't possible, because of Euler theorem that says "(...) Every vertex of this graph has an even degree", and every time I've drawn $G$, in $\overline{G}$ always was a vertex with an odd degree. I'm not sure if it's a rule but it seems to be a proper way of solving the problem. But I'm not sure, hence my question.

## 2 Answers

Hint If $G$ has $n$ vertices, then the degree of a vertex in $G$ plus the degree of the same vertex in $\bar{G}$ is $n-1$. You know that $n$ is even, this means......

• so every vertex $v$ in $G$ and the same vertex in $\overline{G}$ must give odd number ($n$-even), so one of the elements ($v$ or $\overline{v}$) must be an odd degree so according to Euler theorem that says that every vertex must have an even degree it is not possible. Correct ? – Filip Kowalski Oct 15 '15 at 21:26
• @user2010564 Correct. I assume that by circuit you mean a closed trail, if the Eulerian circuit could have different start and end points, then there would be one more case to disscuss :) – N. S. Oct 15 '15 at 22:55

Break it up into two cases. First assume that $G$ is connected and then assume that $G$ is not connected.