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:

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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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.

Log in to reply

Nice! Trémaux's Maze solving algorithm is also related to this.

Log in to reply

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~

Log in to reply

OOPS I'm so sorry :(

Done

Log in to reply

I was just kidding :p

Log in to reply