Olpers
Aug 26, 2018

Olpers
Aug 25, 2018

Olpers
Aug 25, 2018

Olpers
Aug 25, 2018

Olpers
Aug 25, 2018

Olpers
Aug 25, 2018

#1**+2 **

We will proceed by contradiction and induction.

Assume that there is no loop. If two bridges connect the same pair of islands, then we have a loop. So, we cannot have two bridges connecting the same islands.

Case 1: Assume now that each island has two bridges. Denote the islands as . WLOG, connects to , connects to , and so on. However, this yields a contradiction since and both have one bridge. To fix this, we can connect them together, which results in the whole graph being a cycle of length . On the other hand, we now have islands and bridges. Uh-oh. Let's try to fix this by adding in an arbitrary bridge connecting and . Now note that we have a cycle connecting which is a contradiction. Thus, if each island has at least two bridges, then there must be (at least) a cycle.

Case 2: If there is an island with less than \(2\) bridges, then we can "ignore" the island and all bridges extending out of the island. We can keep performing this operation until all islands have at least \(2\) bridges. Now, by Case 1, we are done.

Otherwise; answered at https://artofproblemsolving.com/community/c243175h1500558_combinatorics_2_induction

Olpers
Aug 23, 2018