Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$

Question: Is it true that $\Gamma$ must either be a complete graph or have prime order?

Terminology and notation:

  • By $N(v)$, I mean the set of neighbours of $v$ in $\Gamma$.

  • By vertex-primitive, I mean that the automorphism group acts primitively on the vertices. In other words, the automorphism group does not preserve any partition of the vertex-set apart from the trivial ones (into singletons or with just one part).


  • It is easy to see that a vertex-primitive graph with two distinct vertices having the same neighbourhood must be edgeless. From this perspective, the question is thus about the first non-trivial case.

  • Complete graphs clearly satisfy the hypothesis.

  • There are indeed non-complete graphs (of prime order) satisfying the hypothesis. For example, cycles of prime order. More generally, let $p\geq 5$ be a prime, let $i\in\{2,3,\ldots,\frac{p-1}{2}\}$ and let $S=\{\pm i, \pm (i+1),\ldots, \pm(\frac{p-1}{2})\}$. Then the Cayley graph $\mathrm{Cay}(\mathbb{Z}_p,S)$ is easily seen to satisfy the hypothesis (with $u=0$ and $v=1$, for example).

  • In fact, computer calculations show that there are no counterexamples up to order $100$, say.

  • $\begingroup$ Any cycle of order $n\geq 5$ satisfies the requirement that there are $u,v \in V(C)$ such that $|N(u)\cap N(v)| = |N(v)|-1$: Let $\Gamma = (\{1,\ldots,n\}, E)$ where $E = \{\{k, k+1\} : 1 \leq k < n\}$ \cup $\{\{1,n\}\}$. Then pick $u=1, k=3$. So we don't need the order $n$ to be prime. - Or did I misunderstand your notion of ''order''? $\endgroup$ Nov 10, 2014 at 13:55
  • $\begingroup$ Right, any cycle satisfies the second part of the hypothesis, but the only cycles that are vertex-primitive are the ones of prime order. $\endgroup$
    – verret
    Nov 10, 2014 at 14:00
  • 2
    $\begingroup$ +1 - great question. Except that when I saw the title, I thought "oh, if anyone can answer that it will be verret..." :-) $\endgroup$
    – Nick Gill
    Nov 11, 2014 at 15:33
  • 2
    $\begingroup$ Nick, graphs with two-transitive groups are not too interesting, as for your second question, if $u$ is adjacent to $v$, then the transposition $(uv)$ is in the group of the graph and so it is the symmetric group and we fall back into your first case. $\endgroup$ Nov 12, 2014 at 1:19
  • 1
    $\begingroup$ @Nick : In that case $u$ and $v$ must have the same neighbours apart from each other. $\endgroup$ Nov 12, 2014 at 23:22

2 Answers 2


Pablo Spiga found a proof a few weeks ago. Together, we then proved a slightly more general result which is now on the arxiv: http://arxiv.org/abs/1501.05046

It is more general in two ways: it deals with digraphs rather than graphs, and it gives some information in general when two vertices have neighbourhoods differing by say $k$, although we only get a complete classification of the graphs when $k=1$, which was the original question. (This is Corollary 4.2.)


Here is a partial solution. If the vertices $u$ and $v$ in the statement of the problem are neighbors, I claim that the graph must be complete. Here is my argument:

Let $D = N(u) \cap N(v)$ so by hypothesis, there is exactly one point in $N(v)$ that is not in $D$. Since I am assuming that $u \in N(v)$ and we know that $u \not\in D$, it must be that $N(v) = D \cup \{u\}$. Now suppose the graph is not complete so there exists a point $x$ not in $N(u)$ and different from $u$. Then $x \not\in D$ and thus $x$ is not in $N(v)$, and certainly, $x$ is different from $v$ since it is not a neighbor of $u$. Also, by the symmetry of the assumption, nothing is changed if we swap $u$ and $v$.

Now let us say that an edge is "good" if it is an image of the edge joining $u$ and $v$ under the automorphism group of the graph. By the primitivity assumption, the graph is connected by good edges. We showed that a vertex $x$ different from $u$ and not connected to $u$ is also different from $v$ and not connected to $v$, and thus $x$ has the same property with respect to any vertex that can be reached from $u$ by a chain of good edges. But this is a contradiction since $x$ can reached. This proves my claim

  • 1
    $\begingroup$ Sorry, but Gordon Royle already finished that case in a comment. $\endgroup$ Nov 20, 2014 at 21:35

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.