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