4 ms·
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
by dpbriggs 6y ago
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.
- ogogmad 6y agoFor 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.
- dpbriggs 6y agoGot it, thanks!
- underanalyzer 6y agoIt’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.