Problem 2. In a group of n people, each person has met exactly d other people of the group, and the remaining n - d - 1 people are strangers to him. Suppose that we know for every two persons whether they have met before or they are strangers to each other. Prove that we can always find a group of size from these n people such that no two of them have met before. Describe an ecient greedy algorithm to nd such a sub-group of people and analyze its running time.

d + 1