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: what is the least number of vertices we need to add?



Regularizing graphs
It is always enough to add k+2 more vertices where k denotes the maximum degree. This is sharp as shown by the graph which is a cycle of length 5 plus two independent edges.


The proof is the following. Add edges between non adjacent vertices whose degree is smaller than k until we can. After we cannot, we have some vertices with degree k and a clique of size l where l is at most k. This means we have l vertices whose degree is at least l-1 and at most k-1. Let us add k+1 or k+2 new vertices to our graph depending on the parity to be specified later. Connect the new vertices to the ones forming a clique such that the degrees of the new vertices differ by at most one from each other. Now we only have to add some edges among the new vertices, thus we have reduced the problem to [degree sequences](http://en.wikipedia.org/wiki/Degree_%2528graph_theory%2529#Degree_sequence) and it is an easy corollary of the Havel-Hakimi theorem that if the parity is correct, then a sequence consisting of only d-1 and d where d is less than the number of vertices is always a valid degree sequence.


