A group of seventeen people

In a group of 17 people, every person has exactly 4 friends (friendship is mutual). Prove that there are two people who don’t know each other and having no mutual friends.

Solution

We use a proof by contradiction. We attempt to construct a graph so that the required proof is false, that is, every pair is either friends or has at least one mutual friend. Then we show that this cannot work, and that something goes wrong when we try to construct such a graph.

Let us represent the entire network of 17 people as a graph with 17 nodes, with a friendship being an edge of the graph. It is given that everyone has 4 friends, and friendship being mutual it follows that the total number of edges, or friendships is or 34.

Next we count the number of paths of length 2. If indeed every pair of people are friends or friend-of-friends, then every pair should be separated by a path of at most length 2.

In the entire graph there are 17 people, thus or 136 pairs of people. We already know that 34 of these pairs are friendships, so counting that out, we have 102 pairs of people who are not friends, and thus in our case are separated by a path length of exactly 2.

This establishes a lower bound for the number of friend-of-friends, as a friend-of-friend might be linked intermediately in more than one way. Furthermore, a friend-of-friend might already be one of the friends.

Next we count friend-of-friends a different way. How would the graph be so that the number of friend-of-friends is a maximal? Intuitively, there cannot be any immediate diamond-shapes (4-cycles) or triangles (3-cycles). We get a maximal of 12 friend-of-friends like this:

Each of your friends have a friendship with yourself (the central node), plus three other friends. None of the friend-of-friends are coincident.

Suppose that everyone is arranged in this optimal way, such that everyone has 12 friend-of-friends. Then how many paths of length 2 are there in all? It turns out that there are , or 102 in all.

This establishes an upper bound for the number of total friend-of-friends: a high number cannot be achieved since each node has its optimal configuration to maximize total friend-of-friends.

But we have the lower bound, , because each pair must be connected; we also have the upper bound, , because more connections per person is not logically possible. So the lower bound is the upper bound, and the total number of friend-of-friends must be exactly 102.

The number 102 is not as important as what the condition implies. In order for this to succeed, each node must be in the optimal configuration. This means that in the entire graph, there must be no 3- or 4-cycles!

Having restricted the graph considerably, let use start by drawing the graph:

We introduce some new notation here. Let the four branches of the graph so far be considered as clusters A, B, C, D, each with 3 nodes in it. Notice there are exactly 17 nodes in the graph.

Consider the node A1. It ‘needs’ to have 4 connections, so where to? The 5 unlabelled nodes are already full. If we connect it to another node in the A cluster (A2,A3), it forms a 3-cycle (to the unlabelled node), which is not allowed. The only option is to connect it to something from a different cluster, say, D3.

Then what should it connect to? If we choose D2 or D1, we get a 4-cycle, again not allowed. So we must choose something from the B or C cluster.

It then follows that A1 is connected to one node in each of the three clusters. But that is not all.

We temporarily put aside diagonal connections (from A to C, or B to D). Now suppose that A1 is connected to B1, which is connected to C1, then to D1, and finally back to A1. This is a 4-cycle!

The only other option is to, instead of A1, connect to A2 (or A3, but they are currently interchangeable). Following, we connect to B2, C2, D2, A3, B3, C3, D3, and back to A1.

So the other nodes have to be connected in a 12-cycle. If we arrange the nodes on a circle, the connections look like this:

Now we have the diagonal clusters. A1 has to be connected to something in C. Suppose we choose C1. Then we have A1 -> B1 -> C1, which creates a 3-cycle. Similarly, if we choose C3, we get A1 -> D3 -> C3, which again creates a 3-cycle. The only option that avoids this problem is C2.

By this logic, it is possible to ‘force’ all six of the diagonals (this time represented by dotted lines):

So our graph is complete. Now all we have to do is find a pair not being friends, or being friend-of-friends. Easier, we can also find a 3- or 4- cycle, which implies the existence of such a pair.

Now despite our best efforts not to introduce 3- or 4-cycles, we inevitably still have a few (although it’s not entirely obvious at a first glance where they are). Do you see it?

Take A2, for instance. It connects to C3, then to B3, to D1, and back to A2. A 4-cycle! We are finished.