22

A well-known problem in graph theory is the Seven Bridges of Königsberg. In Leonhard Euler's day, Königsberg had seven bridges which connected two islands in the Pregel River with the mainland, laid out like this:

enter image description here enter image description here

And Euler proved that it was impossible to find a walk through the city that would cross each bridge once and only once. And more generally, that an Eulerian path does not exist for a graph with more than two nodes of odd degree.

World War 2 changed the topology of the city by destroying two of the bridges. (It also brought other changes such as the transfer of the territory from Germany to Russia, but this is not topologically relevant.) This lead to the similar but solvable problem of the Five Bridges of Kaliningrad.

enter image description here

I doubt that the British and Soviet air forces made creation of an Euler walk a priority when they were conducting their attacks. But if they had, one would have to criticize their inefficiency, because they could have achieved the same objective by bombing only one bridge:

enter image description here

Generalizing the problem:

What is the minimum number of edges that need to be removed from a graph so that the remaining edges form an Eulerian path?

My first conjecture was that it would be half the number of “extra” odd degree nodes. However, a simple X-shaped graph provides a counterexample: There are 4 odd nodes (and 1 even one), but two edges need to be removed, not just one.

enter image description here

Dan
  • 14,978
  • 6
    If you want a universal minimum (i.e. one that works for all graphs) then you'll be disappointed. Suppose there is some real number $0\le \alpha\le 1$ such that we can remove $\alpha$-percent of the edges of any graph to produce an Eulerian graph. Your example of the X-shaped graph generalized into a star-shaped graph with one central vertex and many leaves. For such a graph, all but two edges must be removed and so we must have $\frac{n-2}{n} \le \alpha$. Letting $n$ grow arbitrarily large, we must have $\alpha = 1$. There needs to be more restrictions on the problem I think. – EuYu Jun 13 '13 at 00:12
  • If there are $D$ vertices with odd degree, then you must remove at least $\frac{D-2}{2} $ vertices, though you will likely need to remove more than that. – Calvin Lin Jun 13 '13 at 00:14
  • @EuYu: Good point. I suppose what I meant is, "Given an arbitrary connected graph, is there a non-brute-force algorithm for finding the number of edges to remove?" – Dan Jun 13 '13 at 00:22
  • Sorry, I meant remove at least $\frac{D-2} { 2} $ edges (not vertices). – Calvin Lin Jun 13 '13 at 00:25

1 Answers1

4

Color the vertices with an odd number of edges white, and the other vertices black. We consider sets of paths, each path from a white vertex to another white vertex. Such a set of paths with a minimal number of edges, that still connects to every white vertex, constitutes a minimum number of bridges to destroy that leaves an Eulerian cycle.

If instead we consider such a set of paths with a minimal number of edges, that connects to every white vertex but two, that will answer the original question, giving the minimal number of bridges to destroy that leaves an Eulerian path.

vadim123
  • 82,796
  • A path is a sequence of edges, that begins and ends at white vertices (i.e. "from" and "to"), but need not have white vertices in its interior. – vadim123 Jun 13 '13 at 00:35
  • Ah, thanks! Why is edge-disjoint required? We can show that if an edge is used an even number of times, it can be removed from consideration. – Calvin Lin Jun 13 '13 at 00:39
  • @CalvinLin, you're right. In a minimum-length set such as we seek, no edge will get used more than once. – vadim123 Jun 13 '13 at 00:44