John is mayor of a city where buildings are linked by roads. Any given pair of adjacent buildings are linked by exactly one road, and roads can be traversed in either direction. Furthermore, the city is connected in that one can reach any building from any other building by traversing some sequence of roads.
Due to budget cuts, John has asked his lead architect Fred to shut down as many roads as possible while maintaining the city's connectedness. Fred states that there are at least two distinct ways of doing this; that is, there are at least two distinct sets of roads that can be shut down to fulfill John's plan. Prove that if Fred is correct, the city must currently contain a cycle.