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