We are given a social network as an undirected graph where v

We are given a social network as an undirected graph where vertices are people and edges represent friendship between them on our network. A \"cover\" is a subset S of people (vertices) such that everyone not in the set S is friends with someone in S We use the following greedy algorithm to find the smallest size cover S possible While the graph is not empty: Select the node n in the graph which has the maximum number of friends (incident edges). Add n to the set S Delete n and all its friends from the graph.

Solution

A. Smallest cover will be 2,3,4,5 or 1,2,3,4

B. By greedy algorithm the cover will be 5,6,7,8,9,10

C. It chooses a cover, but may not be the minimal cover