Alternatives to the politician theorem

Question

A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R and S are invited to a birthday party. We are told that:

• each pair of guests have exactly one common friend
• A and G only have one common friend: C
• A and G are friends
• I and C only have one common friend: A

How many friends does the most popular (in terms of friends) guest have ?

Invoking the politician/friendship theorem: it is straightforward that A has the most friends (18), as he is the common friend to all the guests.

My question is: can anyone think of an alternative solution to this problem ?

Answer 1

The solution, where $A$ (or $C$) is in the centre of windmill graph is the only solution that gives us 18 friends.

Assume, that A knows everybody. Both A and E have to know someone else, let's say F. Then we have the cycle AEF. The 'windmill' solution gives us 9 'separable' cycles with only common A. Let's try two cycles, that aren't 'separable' (have two common vertices) - AEF and AED. Then A and E have two common friends - F and D. The cycles have to be then 'separate'.

Answer 2

I had never encountered this surprising theorem - thanks for posting.

In order to give a concrete example, the question adds some extra conditions. Under these $A$ has at least three friends: $G$ (by the second condition) and $I$ & $C$ (by the third condition). Therefore it is $A$ who is the politician. Note that this implication was invalid until Alex Ravsky added the second condition. Also the first condition ($C$ the common friend of $A$ & $G$) is redundant.

Shorn of these conditions, the ask is for alternative proofs from the one in "The Book in which God keeps the most elegant proof of each mathematical theorem". That's a fair question but a tall ask. Erdős & spectral analysis have both proved very powerful in graph theory, and we are asked to turn our backs on both...

Here's a different approach based on triangles. It doesn't lead to the full result yet, but I will keep playing with it, and maybe it will inspire someone else.

With no assumptions about regularity for now, for any vertex $A$ with degree $d_A$, there are $C(d_A,2)$ unordered pairs of adjacent vertices. We are going to triage each of the $\sum _{A \in G} C(d_A,2)$ cases. Suppose $B$ & $C$ are two vertices adjacent to $A$. There are two possibilities:

(1) If $B$ & $C$ are non-adjacent, then as $A$ is the "sole mutual friend" of $B$ & $C$, there is a one-to-one-correspondence to the set of non-edges in $G$, of which there are $C(n,2) - m$ items.

(2) If $B$ & $C$ are adjacent then, with $A$, the three vertices form a triangle $ K_3$. Because each vertex is the "sole mutual friend" of the other two, each edge in $G$ belongs to exactly one such triangle. And each such triangle is discovered exactly three times in our examination, depending on which of the three vertices is discovered first. So if $m$ is the number of edges in $G$, there are hence $3 \times m/3$ = $m$ items to be counted here.

Adding these two populations: $m + C(n,2) - m = C(n,2)$

So $\sum_{A \in G} C(d_A,2) = C(n,2)$. [Equation *]

If we require also that $G$ is $k$-regular, then we derive:

$n \times C(k,2) = C(n,2)$

=> $n = k^2 - k + 1$, which is indeed an equation from The Book, so we are on the right track.

Equation * is satisfied happily by all the actual (windmill) solutions. If one "politician" vertex $A$ has degree $2p$, and the other $2p$ vertices have degree $2$, for any $p \ge 0$, then $n = 2p+1$. Then:

$C(2p,2) + 2p \times C(2,2) = 2p\times (2p-1)/2 + 2p \times 1 = p(2p-1)+2p = p(2p+1) = C(n,2)$.