112k views
3 votes
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.

User Robthewolf
by
8.3k points

1 Answer

1 vote

In graph theory, a cycle is a path in a graph that starts and ends at the same vertex, passing through a series of distinct vertices. A connected graph has a path between every pair of vertices. If Fred is correct, there must be at least two distinct sets of roads that can be shut down while maintaining the city's connectedness. A tree-like structure without cycles would have no loops or cycles formed by the roads, and shutting down any road would disconnect the city. Therefore, if Fred is correct and there are at least two distinct sets of roads that can be shut down while maintaining the city's connectedness, it implies that there must already be a cycle in the city.

For example, if a city has four buildings connected by roads, shutting down the road between B and C would disconnect the city. However, if there is a cycle formed by the roads, shutting down any road would still maintain the connectedness of the city. For example, shutting down the road between B and C would still allow us to reach any building from any other building by traversing the remaining roads. Therefore, if Fred is correct and there are at least two distinct sets of roads that can be shut down while maintaining the city's connectedness, it implies that there must be a cycle in the city.

User MCF
by
8.5k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.