Prove it's possible to traverse all bridges in Konigsberg exactly twice returning to the start afterwards

Question

Prove it's possible to traverse all bridges in Konigsberg exactly twice returning to the start afterwards

I don't really know how to prove this. I think I can prove it just by drawing from every point that there is a way back to itself with twice traversal allowed at every edge, but I think that proof is kind of boring. There's a lemma in graph theory that if each vertex has at least degreee 2 there's a cycle, so with that I know there's a possible way back to a starting point I just don't know how to prove it can be done in 2 traversals of each edge.

Answer 1

You could prove it by example (just drawing a path). If you want to prove it more abstractly, consider replacing each bridge (edge in the graph) by two parallel bridges (parallel edges). Now Euler's Theorem says a graph has an Eulerian circuit (a path traversing each edge exactly once and starting and ending at the same vertex) if and only if every vertex has even degree. What are the degrees of the vertices when you double the bridges? Can you convert the Eulerian circuit in the graph with parallel edges to a path in the original graph that traverses every edge twice?

Answer 2

If we replace every bridge by two edges, we obtain a connected graph where every vertex has even degree. In such a graph, Euler cycles exist.