Let $G$ be a simple graph (undirected, no loops or parallel edges), with maximum degree $\Delta(G)$. I would like to add edges to the graph to make it regular, without increasing the maximum degree.
In general this is not possible. (For example, take the 5-vertex graph formed by taking a triangle ($K_3$) and adding two pendant edges to different vertices.)
However, what if we are also allowed to add vertices? I think I can see how to do it by creating many copies of the graph - so my question is: can we do it by only adding $O(1)$ what is the least number of vertices we need to add?
