9.8

Q:
There are 2n + 1 people with the property that, for any n of them, there is some one of the 2n + 1, not among the n, acquainted with all n. Show that there is a person that is acquainted with every one present.
A:
The problem has been characterized as a quickie: once you hit on the right idea, the solution takes just a few lines.

The problem has a natural representation as a graph: two nodes are connected by an edge iff the fellows they represent are acquainted. The nice idea that makes the problem a quickie is that, under the conditions of the problem, there is always a clique of size at least n + 1. A clique is a term for a subgraph that, as a graph, is complete.

Let's first show that the existence of a clique C of size n + 1 leads to a solution of the problem. Let R be the remaining nodes. By the conditions of the problem, there exists a node outside R that is connected to every node in R. Since this node belongs to C (in which all the nodes are connected to each other), this node is connected to all other nodes.

Now, let's form a clique of size n + 1. Pick any n nodes. There is a node that is connected to each of the selected ones. This one, along with any of the selected, form a clique of size 2. Arbitrarily add n - 2 nodes to these two. There is a node that is connected to each of the selected ones. Along with a 2-clique it forms a 3-clique. We may continue in this manner until we get an n-clique. For this, as for any collection of n nodes, there is a node connected to each of the selected ones. Together they form an (n + 1)-clique.