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:

##### Image credit Jake Lai

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

## Comments

Sort by:

TopNewestYes, 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. – Ivan Koswara · 1 year, 11 months ago

Log in to reply

Trémaux's Maze solving algorithm is also related to this. – Daniel Liu · 1 year, 11 months ago

Nice!Log in to reply

– Ivan Koswara · 1 year, 11 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.Log in to reply

Credit me~ – Jake Lai · 1 year, 11 months ago

Log in to reply

Done – Daniel Liu · 1 year, 11 months ago

Log in to reply

– Jake Lai · 1 year, 11 months ago

I was just kidding :pLog in to reply