I think this is possible.

First note that it if the graph is disconnected it is trivial.

Consider two copies of this graph:

[![][1]][1]
<!-- source: https://s8.postimg.org/h1httar05/graphmo.png -->


Vertices $4$ and $5$ are degree $3$ and all other are $4$.

Vertex $3$ is not adjacent to $4$ or $5$.

Connect $4$ to $4'$ and $5$ to $5'$ in the other copy to get
$4$ regular graph with $3,3'$ having all their neighbourhood in the
two copies.

The edges:

    [(0, 3), (0, 4), (0, 5), (0, 6), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6)]


 [1]: https://i.sstatic.net/uubht.png