13 bridges problem

A river has six islands connected by a system of bridges as shown to the right (islands and river banks are green, bridges are gray). A flood has destroyed some bridges: each bridge is destroyed with probability 1/2, independent of the others. What is the probability that after the destruction one can cross the river from left bank to right using the remaining bridges?

We draw in black the graph whose vertices are the places a pedestrian can be and whose edges are the 13 bridges.

Then we consider a ship that wants to sail down the river but can't pass under a bridge. We draw, in blue, the graph whose vertices are the places the ship can be and whose edges are the 13 bridges.

(The two graphs are dual in the plane.)

The ship can pass through a bridge iff it has been destroyed and the pedestrian can't cross it. The black and the blue graph are identical, so each has an equal chance of being able to reach her destination. The ship can pass down the river if the pedestrian can't reach the far bank. So each must have probability ½ of being able to reach her destination.

The 13 Bridges Problem

Hint show

Solution show