Is it true that an Euler path should have two vertices of odd degree and an Euler circuit should have no vertices of odd degree? Is it therefore impossible to have a graph with both an Euler path and an Euler circuit?

  • 1
    $\begingroup$ Every Euler circuit is automatically an Euler path. $\endgroup$ – Wojowu Aug 8 '15 at 21:04
  • $\begingroup$ @Wojowu I disagree. Your comment is in contrast with the last sentence of this link: ohschools.k12.oh.us/userfiles/223/Classes/34/7_Nov25.pdf You might be confusing a Hamilton circuit with an Euler circuit. $\endgroup$ – Julia Aug 8 '15 at 21:13
  • $\begingroup$ @wojowu I have the same doubt as julia. Please, clear the doubt. $\endgroup$ – SARTHAK GUPTA Feb 1 '18 at 9:57
  • $\begingroup$ @SARTHAKGUPTA This all depends on how you define Euler paths and circuits. For example, following the definitions on Wikipedia, Eulerian circuit is just a special kind of Eulerian path. $\endgroup$ – Wojowu Feb 1 '18 at 10:39

This link (which you have linked in the comment to the question) states that having Euler path and circuit are mutually exclusive. The definition of Euler path in the link is, however, wrong - the definition of Euler path is that it's a trail, not a path, which visits every edge exactly once. And in the definition of trail, we allow the vertices to repeat, so, in fact, every Euler circuit is also an Euler path.

  • $\begingroup$ Is it not true that an Euler path has exactly two vertices of odd degree and an Euler circuit has no vertices of odd degree? $\endgroup$ – Julia Aug 8 '15 at 21:18
  • $\begingroup$ What you say for Euler circuit is true, but for Euler paths - no, because (as already mentioned) Euler path can have the same start and end vertex. For example, consider an Euler path on triangle graph which just visits every edge in order. $\endgroup$ – Wojowu Aug 8 '15 at 21:20
  • $\begingroup$ I found this Theorem in Rosen's Discrete Mathematics and Its Applications: A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has an even degree and it has an Euler path if and only if it has exactly two vertices of odd degree. $\endgroup$ – Julia Aug 8 '15 at 21:21
  • $\begingroup$ In that case, Rosen might be using a different definition of Euler path than the one I use. $\endgroup$ – Wojowu Aug 8 '15 at 21:22
  • $\begingroup$ What is your definition? Perhaps Rosen uses the same definition as the link that I provided which you say is wrong. $\endgroup$ – Julia Aug 8 '15 at 21:23

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.