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

  • 5
    $\begingroup$ There are tons of obvious examples: every balanced complete multipartite graph, etc. Heck, even a $4$-cycle. Definitely not research level. $\endgroup$ – verret Jan 16 '19 at 8:40
  • $\begingroup$ 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. $\endgroup$ – Martin Rubey Jan 17 '19 at 19:56

An example with $k = 4$ is the octahedron.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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 $\endgroup$ – Vincent Jan 16 '19 at 8:22
  • $\begingroup$ Why the downvote? I thought everybody loves Platonic solids? $\endgroup$ – Vincent Dec 30 '19 at 20:57

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