Cities and the river [Iran Second Round 1992]
Source:
November 28, 2010
graph theorycombinatorics proposedcombinatorics
Problem Statement
There are some cities in both sides of a river and there are some sailing channels between the cities. Each sailing channel connects exactly one city from a side of the river to a city on the other side. Each city has exactly sailing channels. For every two cities, there's a way which connects them together. Prove that if we remove any (just one) sailing channel, then again for every two cities, there's a way that connect them together.