4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Now that you have posted this question, a list of "Related" existing posts appear on the right. Some of them might be helpful. $\endgroup$ – Lee David Chung Lin Apr 23 at 14:41
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why must $x$ be adjacent to $w_2,\ldots w_k$? $\endgroup$ – Mike Apr 23 at 17:33
  • 1
    $\begingroup$ Yes, this is very good and should be accepted as the correct answer. While I personally would have liked to see this problem proven using Ramsey theory, this proof is correct. The one thing I would like to add is that it's unnecessary to assume that $G$ is connected since that is already implied by property 2. $\endgroup$ – Ryan Greyling Apr 23 at 17:50
  • 1
    $\begingroup$ @RyanGreyling Oh. Yeah. You're absolutely right. Thanks! $\endgroup$ – Santana Afton Apr 23 at 17:58
  • 1
    $\begingroup$ @RyanGreyling I think the best proofs use as little as possible. So I think that this was proved using something close to first-order principles to be a plus. $\endgroup$ – Mike Apr 23 at 18:32
  • 1
    $\begingroup$ I'm not sure what "using Ramsey theory" would even mean if graph-theoretic arguments don't count. Something like 50% of Ramsey theory is just this style of argument. $\endgroup$ – Misha Lavrov Apr 24 at 6:04
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It appears that this argument only shows that there are a very limited set of values of $n$ such that the properties can be met. So rather than demonstrating that the theorem is false, it provides an avenue for proving the theorem by considering only those values of $n$. $\endgroup$ – Mark Fischler Apr 23 at 15:45
  • $\begingroup$ @MarkFischler I see your point. To me, the question seemed to ask for a proof for the general case and my intention was to show that it is not true for an arbitrary $n$. I'm editing my answer a bit in a moment. $\endgroup$ – rss Apr 23 at 16:00
  • $\begingroup$ The author is definitely not asking for a proof of the general case. Anyone could see that the statement doesn't hold for $n=2$ for example. While your answer does show that if the statement is true then there are only four graphs satisfying the statement, it doesn't do anything to actually prove the statement. Hoffman-Singleton theorem only applies when we already know the graph is $k$-regular. $\endgroup$ – Ryan Greyling Apr 23 at 16:05
  • $\begingroup$ @RyanGreyling As I understood the question, the statement we want to prove is the graph $G$ defined in my answer is regular if the conditions described in the question hold. If you were able to prove it for a general $n$, that would contradict the Hoffman-Singleton theorem. Also, there are graphs satisfying the conditions and not being regular. $\endgroup$ – rss Apr 23 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.