In the parliament of Neverland, all legislative work is carried out in committees of three people. The constitution dictates that any four people can be in at most two committees. We call a collection of committees a clique if any two of them have exactly two people in common, and any manner of including another committee in the collection would break this condition. Prove that two different cliques cannot have two committees in common.
, 2015
Solutions — 2
Solution 1
It is easy to see that, given three different committees, each pair of them can have two people in common only if all three committees share the same two people, for otherwise the people in the committees would contain four people from whom three committees have been formed. As a corollary, for any clique, there are some two people who belong to all the committees in the clique, and these people are unique.
To derive a contradiction, let us consider two cliques and with two committees in common. There are some two people and who belong to all the committees in . These two people must also belong to the two committees shared by and . But then all the committees in must also include and . Now, we can extend the clique into , which violates the definition of a clique. □
Solution 2
Consider three committees in a clique. As above, each pair of them can have two people in common only if all three of them share the same two people. Therefore, all committees in a clique share the same two people, and the clique with intersection consists, by maximality, of all possible committees
The clique is thus uniquely determined by the intersection of any two of its elements. □