Possible Duplicate:
Proving that every graph is an induced subgraph of an r-regular graph
** Sorry for the repost but I was unable to respond to any comments to the previous submission presumably because I was not registered.
How would you prove that every graph G is an induced subgraph of an r-regular graph where r >= D and D is the largest degree of the vertices of G?
I can picture the answer for when G itself can be turned into a D-regular graph: make a union of G with a copy of itself and then connect the vertices across the two vertex sets U (from G) and W (from the copy of G) such that u_i and w_j are connected if and only if v_i and v_j would be connected in the original graph in order to turn it (the original graph) into a D-regular graph.
However, I cannot figure out how to do it in the general case where, for instance, the order of G may be even or odd (and, thus, may not be made into an r-regular graph if r is odd as well) or for when r > D. (I am also having trouble with the just language of graph theory and how to write proofs for it if you couldn't tell.)
