Return to Revisions

Let $k = 2 \lceil {r \over 2} \rceil$ and start with $G_k = k \cdot G$ such that we have $k$ copies of $G$ and, thus, $k$ copies of each vertex $v \in V(G)$. Next, partition $G_k$ into $n=|G|$ subsets $G_1,...,G_n$ such that each consists of the $k$ copies of vertex $v_i \in V(G)$. Each element in a given subset has degree $d_i \leq r $ and is adjacent to no other element in the subset, thus, we can form a $(r-d_i)$-regular subgraph amongst the vertices in a particular subset. We know this is possible because each subset has an even number of elements ($k$ was defined to be even). Performing this for all subsets $G_1,...,G_n$ will result in an r-regular graph $G_k$ of order $kn$. Finally, since all of the added edges run only between copies of the same vertex, any subset of $V(G_k)$ corresponding to one of the $k$ copies of $V(G)$ will induce the original graph $G$.