Homework answers / question archive / 1) Petros is mayor of a city where buildings are linked by roads

1) Petros is mayor of a city where buildings are linked by roads

Math

Share With

1) 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.

2) We have a room full of n people. Any given pair of people are either
friends or strangers. In this room, Alex is considered the most popular
because he has k friends, and no other person in the room has more than
k friends. Prove that we can find a group with at least n
k+1 people such
that no two members of the group are friends.