# Regular graph such that $2$ distinct vertices have same neighborhood set [closed]

If $$G=(V,E)$$ is a simple, undirected graph and $$v\in V$$, we set $$N(v) = \{w\in V:\{v,w\}\in E\}$$.

Is there an integer $$k>1$$ and a connected $$k$$-regular graph $$G=(V,E)$$ such that there are $$v\neq w \in V$$ with $$N(v) = N(w)$$?

(Note that the definition of $$N(\cdot)$$ implies that $$v,w$$ cannot be adjacent.)

• There are tons of obvious examples: every balanced complete multipartite graph, etc. Heck, even a $4$-cycle. Definitely not research level. – verret Jan 16 '19 at 8:40
• The $4$-cycle is nice because it is the only cycle that has a pair of vertices sharing the neighbourhood. The number of graphs without any pair of vertices sharing the neighbourhood (apparently called mating graphs) is oeis.org/A004110. Enumerative results using modern methods can be found in arxiv.org/abs/0705.0042, it may be interesting to refine this to regular graphs. – Martin Rubey Jan 17 '19 at 19:56

An example with $$k = 4$$ is the octahedron.
• This has the additional property that for every $v$ there is a $w$ such that $N(v) = N(w)$. If we just want one pair $(v, w)$ with the property we can easily just make countless such graphs by first drawing $v, w$, their neighbors and the edges from $v$ and $w$ to said neighbors and then keep adding vertices and edges until the result is regular again – Vincent Jan 16 '19 at 8:22