Graph Theory:
Use Graph Theory:
Petros 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, Petros has asked his lead architect Kik to shut down as many roads as possible while maintaining the city’s connectedness. Kik 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 the mayor’s plan. Prove that if Kik is correct, the city must currently contain a cycle.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
