4 ms·
Nitpick: the bridge problem is impossible because there aren't 2 or 0 nodes of odd degree. If you have 2 islands with three bridges connecting them, you could
by lordnacho 6y ago
Nitpick: the bridge problem is impossible because there aren't 2 or 0 nodes of odd degree.
If you have 2 islands with three bridges connecting them, you could just walk them trivially, yet there are an uneven number of connections on each node.
- dpbriggs 6y agoI 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.
- dmurray 6y agoTFA specifies the bridge problem in the form where you have to "end up back home", so its conclusion is correct.
- gbjw 6y agoExcept that, if I understand correctly, the author poses the problem such that one must 'end up back home' (that is, one must find an Eulerian circuit, not a path). If there are 2 nodes of odd degree, then you must start at one and end at the other.