# Regularization of arbitrary graphs

Let $$G=(V,E)$$ be a finite, simple, undirected graph. Let $$\Delta(G)$$ be the maximal degree of $$G$$. Is there a finite graph $$G'=(V', E')$$ with the following properties?

1. $$V\subseteq V'$$,
2. $$E \subseteq E'$$, and
3. $$G'$$ is $$\Delta(G)$$-regular.
• In other words, if $\Delta\ge d_1\ge d_2\ge\dots d_n\ge 0$, then $\Delta,\dots \Delta, d_1\dots d_n$ is a graphic sequence for some number of repetitions of $\Delta$. Looks obvious, doesn't it? – fedja May 22 at 7:23
• @fedja not quite just graphic sequence, we should save the existed edges – Fedor Petrov May 22 at 7:29
• @FedorPetrov $d_j$ are $\Delta$ minus the existing degrees, i.e., I'm looking for the complement. I thought that was clear enough :-) – fedja May 22 at 7:31
• @fedja well, but the complement should avoid existed edges, right? – Fedor Petrov May 22 at 7:36
• @FedorPetrov Indeed, you are right. The correction is trivial (add some edges sticking out to saturate the existing vertices and consider the new graph), but then it basically becomes your construction. – fedja May 22 at 7:53

Yes. First of all, for any vertex $$v\in V$$ we draw the edges to $$\Delta(G)-\deg(v)$$ new vertices so that the degree of $$v$$ becomes equal to $$\Delta(G)$$. Now all degrees are equal either to $$\Delta(G)$$ or to 1. Without loss of generality, the number of vertices with degree 1 is even (else add the disjoint copy of the current graph). Partition them onto pairs, and for any pair $$a,b$$ take a graph $$K_{d+1}\setminus \{ab\}$$ on the vertex set $$\{a,b, d-1\, \text{new vertices}\}$$.