We are at a party and we realize that each guest has exactly one friend in common with every other participant, so we ask ourselves if there is someone who knows all the guests. The answer is yes, the Friendship Theorem – not to be confused with the Friendship Paradox – a theorem concerning graph theory that was first proved in 1966 by three Hungarian mathematicians Paul Erdős, Alfréd Rényi and Vera T. Sós. Let’s see how the theorem works in the case of a party and what this has to do with windmills.
The situation is this, we find ourselves at a party where a particular situation occurs:
each guest has exactly one friend in common with every other guest, no more, no less.
The Friendship theorem then tells us that
among all the guests there is exactly one who is a friend of all the guests.
Let’s see, with an example, why this happens. Let’s suppose that the first to arrive at the party were Marta, Edo and Marco, and that all 3 of them are friends with each other so, taken two by two, they have exactly one friend in common: Marta and Edo have Marco as a mutual friend, Marco and Edo have Marta as a mutual friend, Marta and Marco have Edo as a mutual friend. Using the language of graph theory we can describe this situation with a scheme (see image below) in which the friendship between two people is represented by a line that unites them.
A scheme of this type is called a graph, the positions occupied by the three friends are called vertices (or nodes) and the lines that unite them – their relationships – are called arcs (or edges).
But let’s go back to the party, among the participants there is also Vale, who is a friend of Marco, but she cannot also be a friend of Marta because, if she were, Vale and Edo would have two friends in common (see figure below), namely Marco and Marta, while at our party two participants can have a maximum of one friend in common. For the same reason Vale cannot be friends with Edo.
At this point, however, there is another problem: Vale and Marco have no friends in common, so there must be at least one other participant in the party, who must be a friend of both Vale and Marco. Luckily, Luca, a mutual friend of Vale and Marco, who is not a friend of either Edo or Marta, also participates in our party. Luca, in fact, cannot be a friend of Edo because otherwise he would have two friends in common with Marco, namely Edo and Vale, and for the same reason he cannot be a friend of Marta.
If there were no other participants at our party, therefore, the situation could only be that of the image below in which one participant, Marco, is everyone’s friend, and the scheme (or graph) representing the situation is made up of 2 triangles with a common vertex.
If we now imagine adding two more participants following the same rules, as we did for Carla and Luca, we cannot do anything other than add a new triangle to the graph that shares with the other triangles the vertex constituted by Marco, the only guest who is everyone’s friend (see figure below).
The graph we obtained is made up of three triangles that share a vertex placed in the center and by continuing to add party participants we would have to add new triangles, all with the same vertex in common, and Marco would continue to be everyone’s only friend. The shape of the graph, as we can see, is a bit reminiscent of the blades of a windmill: according to the Friendship Theorem, in fact, any party that verifies the same rules as our party can be represented with a graph in the shape of a windmill.
