Minimal regular graph containing a given graph (Q1187918)

Given a graph \(G=(V,E)\) on \(n\) vertices with a maximum degree \(d\) of points of \(G\), there exists a \(d\)-regular graph \(H\) on \(n+m\) vertices containing \(G\). (``\(G\) can be realized as an induced subgraph of \(H\).'') Using an extension of a theorem of Erdős and Kelley the paper shows that every \(G\) can be realized as an induced subgraph of a regular graph on at most \(2n-2\) vertices and that this \(m=2n-2\) is the minimal one. Some related results are also deduced.