**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).




---


**Comments:** 


* 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.



Vertex-primitive graphs with two vertices having almost the same neighbourhood
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.)


