Remove bridges to make finding a path impossible.

Question

Here's a question relating to graph theory that was asked in the International Kangaroo Maths Contest 2017. I am a college student and have a very less knowhow of graph theory. The question goes like this:

We have $10$ islands that have been connected by $15$ bridges.

What is the smallest number of bridges that may be eliminated so that it becomes impossible to get from $A$ to $B$ by bridge?

Answer: The answer given in the key is $3$, but I can't see how that might be.

What I did:

First of all I transferred the problem into graphical terms.

We have $10$ vertices connected by $15$ edges.

What is the smallest possible number of edges that when removed to make it impossible to find a path from $A$ to $B$?

So I considered that we can do this by 'isolating' either $A$ or $B$. This may be done by removing all the edges corresponding to either $A$ or $B$. The number of edges corresponding to $A$ is $4$ while those with $B$ are $5$. So the smallest number that can be the answer is $4$. So what is wrong with this method? How can be the answer, $3$, be reached?

Thanks for the attention.

Answer 1

MathFun123's answer shows that it is possible to remove three edges in this way, but not that three is the minimum.

To see that you can't do it with less than three, consider the following.

There are three completely separate paths from A to B shown. In order to cut off B from A, you need to remove at least one red edge to destroy the red path, and similarly at least one blue edge and at least one green edge. So at least three are needed.

Answer 2

By removing the red lines $A$ and $B$ are isolated; in other words: no path is possible from $A$ to $B$.

Answer 3

"So I considered that we can do this by 'isolating' either A or B"

I tried the same thing at first. As a general approach to problems like this though, you should try to confirm that your supposed methods are actually the most efficient. Isolating either A or B is a good starting point, however, as the other answers have shown you, it's not a complete solution.

"So what is wrong with this method?"

The reason your method failed is you made a faulty assumption: that any two paths must converge only on island B. Were that true, then isolating either A or B (whichever had fewer brides) would work; if the number of paths could only increase until converging on B, then A would have to have the fewest bridges (and vice versa).

However, we know that this isn't true, and in this example, it becomes relevant with the top two paths stemming from island A; they converge on pretty much the next island. This shows us that you can remove one fewer bridge by waiting until they converge on that island than by isolating A immediately.

"How can be the answer, 3, be reached?"

A more effective approach would be to still start where you started: by isolating A. That's at least 4 bridges you have to remove. From that point though, you have to travel each path and see if at any island the number of paths to B decreases or increases. That will help you pick the most efficient bridge to remove for any given path.

For example, lets follow the bottom-most path from A. After it's first island, there is still only one path to B. After it's second island though, this splits into two paths to B. Now that's two bridges you have to deal with instead of one, so we can safely remove the first bridge on this path. The same applies to the second bottom-most path.

As for the upper two paths, we can see the second island for the upper-most path is the same as the first island for the second upper-most path (I really wish they labeled each island). Rather than splitting into two paths, at this island two paths merge into one. This lets us remove both of the upper-most paths by removing one bridge, which takes our total bridges to remove down to 3.

In this example, 3 is the best we can get. However, we can also apply this approach to any graph and achieve the best outcome (it should be noted that just because a path splits into two, it shouldn't be immediately thrown out. There's still a chance both of those paths will converge on another one, that just didn't happen in this example).

Answer 4

A rigorous but overengeneered answer would be as follows: Let us consider the graph as a flow network with unit capacities. Then after finding exactly three paths in the remainder network the target becomes unreachable in it, so by the Ford-Fulkerson theorem the minimal cut has three edges in it, which can be easily found found on aforementioned paths, as only they connect vertices reachable from source in the resulting remainder network with unreachable ones. Now if it s possible to remove less edges to make A unreachable from B, it would contradict the definition of a minimal cut, therefore we've found exactly what was asked of us.