I learned that

A connected graph has an Eulerian path if and only if it has at most two vertices of odd degree.

However, because of the term "at most", I'm very confused. What if a graph has $0$ vertices of odd degree, which satisfies "at most". Then does the graph have an Eulerian path?

I thought that a connected graph with $0$ vertices of odd degree has a Eulerian circuit.

Does "Eulerian path" include "Eulerian circuit"? Aren't the definitions of path and circuit definitely differently?

  • $\begingroup$ A connected graph has an Eulerian path if and only if etc., etc. $\endgroup$ – Gerry Myerson Apr 10 '18 at 11:07
  • $\begingroup$ @GerryMyerson That is not correct: if you delete any edge from a circuit, the resulting path cannot be Eulerian (it does not traverse all the edges). If a graph has a Eulerian circuit, then that circuit also happens to be a path (which might be, but does not have to be closed). $\endgroup$ – dtldarek Apr 10 '18 at 13:08
  • $\begingroup$ If "path" is defined in such a way that a circuit can't be a path, then OP is correct, a graph with an Eulerian circuit doesn't have an Eulerian path. $\endgroup$ – Gerry Myerson Apr 10 '18 at 21:36

A Euler path goes through every edge once. A Euler circuit goes through every edge once and starts and ends at the same vertex. Therefore, Euler circuits are a subset of Euler paths.

Did some research from Euler Paths and Circuits


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.