I think this is possible.
First note that it if the graph is disconnected it is trivial.
Consider two copies of this graph:
http://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)]