Show that, in a group of n people, everyone has the same number of friends if..

Question

Question:

Consider a group of n people with the following properties:
• no person is friends with everyone,
• any pair of strangers share exactly one friend in common,
• no three people are mutually friends.
Show that everyone has the same number of friends.

I want to solve this using Ramsey's theorem but I'm struggling to formulate it in a way that would make it straightforward.. Any help would be greatly appreciated.

Answer 1

I don't believe this is true for $n$ in general. Let's define the graph $G$ such that the nodes correspond to the people and two nodes are adjacent iff the corresponding people are friends. If everyone had the same number of friends, $G$ would be a strongly regular graph with parameters $(n, d, 0, 1)$ (by the last two conditions). In this case $n$ must equal to $d^2 + 1$ and the second condition implies $d \geq 2$.

However, the Hoffman-Singleton theorem states that $d \in \{2,3,7,57\}$ for strongly regular graphs with parameters $(d^2 +1, d, 0, 1)$, where $d \geq 2$. Therefore, the statement of your problem can be true in at most 4 cases.

Edit 1: Special cases

It is known that if $d \in \{2,3,7\}$, the parameters uniquely define $G$. These graphs are $C_5$, the Petersen graph and the Hoffman-Singleton graph, respectively. It is currently an unsolved problem whether a strongly regular graph with parameters $(3250, 57, 0, 1)$ exists.

Answer 2

This solution was created joint with Skye Binegar.

---

Assume that these conditions hold of a graph $G$. I'm going to enumerate your properties as

1. No vertex is adjacent to every other vertex.
2. Any two non-adjacent vertices are both adjacent to a single unique vertex.
3. No triangles exist.

Let $v$ be a vertex of highest degree, say $k$, and let $v_1,\dots, v_k$ be its neighbors. Note that by $(3)$, no two neighbors of $v$ are adjacent. By $(1)$, there is some vertex $x$ that $v$ is not adjacent to. Since $v$ and $x$ are not adjacent, by $(2)$ there is a unique $v_i$ such that $v_i$ is adjacent to $x$. Let's assume that $v_1$ is this vertex.

Now, for every $2\le i\le k$ we see that $v_i$ cannot be adjacent to $x$ by uniqueness of $v_1$ guaranteed by $(2)$. Therefore, for each $i$ there must exist some unique vertex $w_i$ adjacent to both $x$ and $v_i$ by $(2)$, since $v_i$ and $x$ are not adjacent when $i\ne 1$. Note that each $w_i$ must be distinct, as otherwise $v$ would be connected to some $w_i$ in two different ways, contradicting $(2)$.

This means that $x$ is adjacent to $v_1$ and $w_2,\dots,w_k$. Since $v$ has the highest degree $k$, and $x$ has degree at least $k$, this shows that $x$ has degree $k$. Therefore, any vertex that is not adjacent to a vertex of degree $k$ must also have degree $k$. Now, note that each $v_i$ is not adjacent to $x$, which we showed has degree $k$. Therefore, this argument shows that each $v_i$ must also have degree $k$.

Therefore, if a vertex has degree $k$ then so do all of its neighbors. By the connectivity of $G$ and maximality of $k$, this proves that $G$ is $k$-regular.