×

Everyone has heard of the famous Königsberg bridge problem, where one must traverse all seven bridges and end up back where one started without traversing a bridge twice. This is indeed impossible, as dictated by Graph Theory.

However, loosening the restriction to we must traverse each bridge exactly twice, we see that it indeed becomes possible:

imgur

##### Image credit Jake Lai

So, is it possible, with these new rules, to successfully traverse through any set of paths (i.e graph)?

Note by Daniel Liu
1 year, 9 months ago

Sort by:

Yes, it's always possible as long as the graph is connected; moreover, it's always possible to find such tour where each edge is traversed once in each direction. The proof is also simple: just double all the edges (and orient them, for the strengthening), and see that the produced graph is Eulerian by inspecting its degrees; any such Eulerian tour has the property that it uses each original edge twice (since each original edge is doubled into two edges, where each of it is used). To find one such path, use some algorithm. · 1 year, 9 months ago

Nice! Trémaux's Maze solving algorithm is also related to this. · 1 year, 9 months ago

Indeed, my first idea was to use depth-first search (which is essentially a variation of Tremaux's maze solving algorithm, or the other way around), but marking edges instead of vertices; this doesn't guarantee that the result is Eulerian, however (some edges might be missed). Thus we can extend the resulting tour to cover all edges, and that's Hierholzer's algorithm. · 1 year, 9 months ago

Credit me~ · 1 year, 9 months ago

OOPS I'm so sorry :(

Done · 1 year, 9 months ago