There are $n$ islands with $n$ bridges connecting pairs of islands (where $n\ge 2$). Prove that some sequence of distinct bridges forms a loop.
I think induction is the way to go; it is clearly true for $n=2$, but I am confused about the inductive step. How should I connect $n$ and $n+1$?
HINT: Suppose that the result is true for $n$ bridges and $n$ islands, and that you have an arrangement of $n+1$ bridges and $n+1$ islands.
If there is an island with exactly one bridge to it, consider the arrangement that remains after you remove that island and bridge.
If there is an island with no bridge to it, consider the arrangement after you remove that island and any one bridge.
Otherwise, each island has at least two bridges. Start at any island. Cross a bridge to another island. Keep moving from island to island, making sure that you always leave each island using a different bridge from the one by which you reached the island. You can do this indefinitely. (Why?) On the other hand, there are only finitely many islands, so eventually ...