In a committee there are members. Each pair of members are either friends or enemies. Each committee member has exactly three enemies. It is also known that for each committee member, an enemy of his friend is automatically his own enemy. Find all possible value(s) of .
Solution
Suppose and are enemies. By the given condition, every other member cannot be a friend of both and . Since each of and has 2 more enemies other than themselves, we must have . Also, as each member has 3 enemies, we have , and there are pairs of enemies. This shows is even, and hence can only be 4 or 6.
To give examples for and , we use terminologies in graph theory. Suppose vertices denote the members and edges join pairs of enemies. Then and are examples for and respectively.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.