co.combinatorics - Regularizing graphs

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

• Next gn.general topology - Name for a kind of topological property?
• Previous ag.algebraic geometry - A Galois Theory Computation