Hint: Recall bipartite graphs, where you have two sets of verticies X and Y, where the verticies of X are only connected to vertices of Y and vice-versa. Which values of X and Y would you choose such that each vertex has degree 4?
sadly, don't think there's an algorithm to always find such graphs. however, the Handshaking Lemma can be useful for showing that some graphs can't exist. (if the sum of the degrees of each vertex is an odd number... what can we conclude?)