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$

2 Answers 2

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$
2
  • $\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$ Oct 15, 2015 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, 2015 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$

You must log in to answer this question.

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