- #1

- 7

- 0

## Homework Statement

How would you prove that every graph G is an induced subgraph of an r-regular graph where r >= D (the largest degree of the vertices of G)?

## Homework Equations

NA

## The Attempt at a Solution

I can picture the answer for when G itself could 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 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 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.)