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
3 years, 1 month ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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.

- 3 years, 1 month ago

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

- 3 years, 1 month 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.

- 3 years ago

Credit me~

- 3 years ago

OOPS I'm so sorry :(

Done

- 3 years ago

I was just kidding :p

- 3 years ago