Regularizing graphs

Question

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?

Answer 1

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 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.

Answer 2

In reply to your original question: You certainly can't add a constant number of vertices independent of the maximum degree -- consider the disjoint union of $K_k$ and a single vertex. This gives a linear lower bound in $\Delta(G)$. (Even if you require that the graph is connected, take a 2-connected regular graph, remove an edge, and add two new pendant vertices adjacent to the endpoints of that removed edge.)

ETA: I didn't notice, but the way you edited the question makes my original answer kind of confusing. Hopefully it reads better now.

ETA^2:

With constant maximum degree you can add a constant number of vertices, although I'm not going to do any close analysis on the exact number -- it should be polynomial, and probably if you're more careful you can even make it linear or at worst quadratic in the maximum degree. Set $\Delta(G) = k$, and note that we can add just edges to get at most $k$ vertices of degree less than $k$; otherwise there'd be two such non-adjacent vertices, and you could add in that edge.

Now we can add $O(k^2)$ pendant edges to make all the original vertices have degree $k$; then we can put in copies of $K_{k+1}$ with an edge removed on pairs of these new vertices. (As long as $k * |V(G)|$ is even, you can check parity to see that this is possible; if it's not, this is remedied by adding a new vertex and connecting it to a vertex which has degree < k before we do anything else.)