Return to Revisions

Here is a simple and "natural" (whatever it means) way to get a regular graph from a given graph $G$. Take two disjoint copies of $G$, and insert edges between all pairs of vertices $(v_1,v_2)$ (with $v_1$ from the first copy and $v_2$ from the second copy) whenever there is no edge between the two corresponding vertices of $G$. Denoting by $n$ the order of the original graph $G$, this way you get an $n$-regular graph of order $2n$.