Reword each of the following statements as a theorem about undirected graphs, and then prove it. Assume
Question:
Reword each of the following statements as a theorem about undirected graphs, and then prove it. Assume that friendship is symmetric but not reflexive.
a. Any group of at least two people contains at least two people with the same number of friends in the group.
b. Every group of six people contains either at least three mutual friends or at least three mutual strangers.
c. Any group of people can be partitioned into two subgroups such that at least half the friends of each person belong to the subgroup of which that person is not a member.
d. If everyone in a group is the friend of at least half the people in the group, then the group can be seated around a table in such a way that everyone is seated between two friends.
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest