# How many people at a party if everyone knows 22 other people and any two who don't know each other have exactly 6 mutual friends?

You are in a strange party where everyone knows exactly 22 other person and any two who don’t know each other have exactly 6 mutual friends. How many are there in the party?

Source 40- Strange Party

My research:

I know that the adjacency matrix $$M$$ is symmetrical and if $$M[i,j] = 0$$ then i-th and j-th rows have 6 times 1 at the same index position. I am thinking about encoding problem into SAT formulae and trying to brute force SAT solver with different number of literals (elements of upper triangle matrix of adjacency matrix).

I have read some articles about Moore graphs and it seems that the upper limit for the vertices is $$22^2 + 1 = 485$$.

Do you have any hints to the solution?

• What is a party? I didn't think that people can be in groups of more than 6 people, let alone where they know 22. Nov 2 '20 at 21:07
• There's a trivial answer of 23 people (everyone knows everyone, so the 6 mutual friends rule doesn't get used). I'm guessing that's not what you're looking for though.
– Dave
Nov 2 '20 at 21:25

This is not a solution. This just demonstrate that $$n \leq 100$$.

Take the typical graph theoretic representation.
Let friend be represented by a red edge, stranger be represented by a blue edge.
We have $$d_r (v_i) = 22, d_b (v_i) = n - 23$$, so total number of red edges is $$11n$$ and total number of blue edges is $$\frac{n(n-23)}{2}$$.

We count the number of triples of red-red-blue triangles.
For each blue edge, the condition gives us exactly 6 red-red-blue triangles.
For each red-red emanating from a vertex, it could give us a red-red-red or red-red-blue triangle.

Hence, $$6 \times \frac{ n ( n-23) } { 2 } \leq n \times { 22 \choose 2 } \Rightarrow n \leq 100$$.

A partial answer: the possible numbers of vertices are $$23, 40, 100$$, and some unknown subset of $$\{51,52, \dots, 99\}$$.

For a vertex to have degree $$22$$, we need at least $$23$$ vertices. This is possible: take the clique $$K_{23}$$. The second condition is satisfied trivially.

If we want the second condition to be satisfied nontrivially, then there must be non-adjacent vertices $$v$$ and $$w$$. This requires $$6$$ more vertices in $$N(v) \cap N(w)$$, $$16$$ more in $$N(v) \setminus N(w)$$, and $$16$$ more in $$N(w) \setminus N(v)$$, for at least $$40$$ total.

$$40$$ vertices is possible: consider the graph with vertex set $$\{v_1, \dots, v_{20}, w_1, \dots, w_{20}\}$$, with a complete graph on the first $$20$$ and the last $$20$$ vertices. Additionally, add edges $$v_i w_i$$, $$v_i w_{i+1}$$, and $$v_i w_{i-1}$$ (with arithmetic modulo $$20$$). Two non-adjacent vertices $$v_i$$ and $$w_j$$ have $$\{w_{i-1}, w_i, w_{i+1}, v_{j-1}, v_j, v_{j+1}\}$$ as common neighbors.

If there are more than $$40$$ vertices, then in the lower bound above there must be at least one vertex $$u$$ not adjacent to $$v$$ or $$w$$. Let's say that $$|N(u) \cap N(v) \cap N(w)| = k$$. Then there are $$6-k$$ vertices in each pairwise intersection of $$N(u), N(v), N(w)$$ leaving $$22 - k - 2(6-k) = k+10$$ vertices adjacent to only one of $$u,v,w$$. That's a total of at least $$51$$ vertices.

I don't know if this is achievable, but there's an upper bound. On the high end, the Higman–Sims graph has $$100$$ vertices, and is an example because it is strongly regular. Every vertex has degree $$22$$, every two non-adjacent vertices have $$6$$ common neighbors, and for a bonus every two adjacent vertices have no common neighbors. As the other answer argues, this is the largest possible number of vertices.

• The first was clever. I'm not seeing your second example though...
– Mike
Nov 2 '20 at 18:45
• I see it now. Thanks!
– Mike
Nov 2 '20 at 18:49
• I also found the 40 vertices example, but wasn't able to adapt it to > 40. Nov 2 '20 at 19:25
• @CalvinLin $41, \dots, 50$ are also impossible, and I have serious doubts about $51$. Nov 2 '20 at 19:38