Induced subgraphs (graph theory) I have the following graph theory question that I am stuck on:
Prove or disprove:
For every graph G and every integer $r \geq \text{max} \{\text{deg}v: v \in V(G) \}$ , there is an r-regular graph H containing G as an induced subgraph. Thanks for any help.
 A: Can you construct an r-regular graph with an arbitrary number of vertices as long as the number of vertices exceeds a given quantity? If so, then you may construct H from G as follows: 
Let be the degree of the nth vertex of G. For every vertex in G with degree less than r, add a vertex to the graph and an edge connecting that vertex to and repeat this process until the degree of is r. Then you will have a graph in which the degree of the vertices originally in G is r, and the degree of the vertices not originally in G is 1. If you cannot construct an (r-1)-regular graph with the number of additional vertices (the ones not originally in G), then add two vertices and connect them with an edge. Repeat this process until you can construct an (r-1)-regular graph with the number of additional vertices. Now, for the vertices whose degree is 1, add the edges of the (r-1)-regular graph you constructed. This will complete the creation of H, and G will be an induced subgraph of H, which is seen easily by choosing the vertices originally in G, to which no edges were added in the creation of H.
A: Let $G$ be a graph with maximum degree $\le r$. Let the vertices of $G$ of degree $\lt r$ be listed (with repetitions) in a sequence $v_1,v_2,\dots,v_n$ where each vertex $v$ occurs $r-\mathrm{deg}(v)$ many times. (So $n=pr-2q$ where $p$ is the number of vertices and $q$ the number of edges in $G$.) Take $r$ vertex-disjoint copies $G^{(1)},G^{(2)},\dots,G^{(r)}$ of $G$; let $v_i^{(j)}$ be the copy of $v_i$ in $G^{(j)}$. Create new vertices $w_1,w_2,\dots,w_n$ and edges joining each $w_i$ to $v_i^{(1)},v_i^{( 2)},\dots,v_i^{(r)}$. Now we have an $r$-regular graph of order $2pr-2q$ containing $G$ as an induced subgraph.
