Hacker News Reader

I may be misremembering my graph theory class, but isn't the necessary and sufficient conditions for an eulerian path just that every vertex needs to have even degree?

I'm not sure how it could work if any nodes had odd degree.

View on HN

For an Eulerian circuit, you need the graph to be connected and for every node to have even degree. For an Eulerian path (which doesn't have to start and end at the same point) you may also allow two vertices to have odd degree.

Got it, thanks!

It’s sufficient but not necessary. Consider a trivial example with three nodes arranged in a chain. The edge nodes at the end of the chain both have degree 1 but walking from one edge to another is an eulerian path.

Reply on news.ycombinator.com