If you do not feel familiar with the material, I suggest that you work through at least the following problems. These are good practice. In order to monitor us, they decide to place look-out posts at street intersections in every major city. Below is the map of Montreal. Vertices correpond to intersections.
Edges correspond to streets.
Billy Bob decides to have a party. He makes a list of people but realizes that certain pairs of people do not get along. If he invites both people from such a pair, there will be a fight and his precious party will be ruined. He decides that, for any pair of people who fight, he will not invite both. Try to find an algorithm that runs in time .