Proof By Contradiction [?]

Question

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.

__

Since it isn't obvious how to prove it directly I think I'm going to argue by contradiction. But I'm not sure how to.

Answer 1

We prove a slightly stronger result, if there are $n$ bridges or more then there is a loop.

Prove it for $n=3$ by checking all possible cases.

We now use induction. Suppose there are $n$ islands. If every island has at least two bridges coming out of it then we can start at any island and keep walking, if we ever reach an island from which we cant go away we must have reached the island before, this argument proves the existence of a loop.

If there is an island which has one or zero bridges then we can delete that island along with its bridges and we will still have a number of bridges larger than or equal to the number of islands, so we can use the inductive step to find a loop, (since there are now $n-1$ islands).

This theorem is a well known theorem in graph theory, it is intimately related with some basic results about trees.

Answer 2

Note: This answer is not meant to indicate that proof by contradiction is the only or best way to prove this theorem.

To prove this by contradiction you would attempt to prove the following statement:

There are $n$ islands with $n$ bridges connecting pairs of islands. When $n\geq 2$ it is impossible to form a loop of bridges.

While trying to prove the above statement, you want to fail to prove it in a specific way. What you want to do is arrive at a statment in your proof that contradicts one or more of the assumptions in the statement of the theorem. Once you have the contradiction, you have established that the above theorem cannot be true. If the above is false, then there must be at least one loop when $n\geq 2$.