Wikipedia's Eulerian Path states,

An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.

But I find a mistake with this. The beginning, S, and end, T, vertices could be joined by single edges to the graph, G, where every vertex (beside S & T) has even degree. You would still be able to visit every edge once, like:

Start at S, go to a vertex in G, Ga, do a Euler tour in G finishing on vertex Gb, end by going from Gb to T.

S and T only have degree 1.

Or have I made a mistake?

  • 2
    $\begingroup$ The definition of an Eulerian cycle is that it ends at the same point that it begins at. Apart from this, your reasoning is correct. $\endgroup$ – Mathmo123 Jun 22 '14 at 12:45

You have found why a graph might have an Eulerian path but no Eulerian cycle.


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.