2
$\begingroup$

(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.

$\endgroup$
1
$\begingroup$

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......

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Filip Kowalski Oct 15 '15 at 21:26
  • 1
    $\begingroup$ @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 :) $\endgroup$ – N. S. Oct 15 '15 at 22:55
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.