Proving that every graph is an induced subgraph of an r-regular graph

Question

How would you prove that every graph $G$ is an induced subgraph of the $r$-regular graph, where $r\geq \Delta(G)?$

I can picture the answer for when $G$ itself can be turned into a $\Delta$-regular graph: make a union of $G$ with a copy of itself and then connect the vertices across the two vertex sets $U$ (from $G$) and $W$ (from the copy of $G$) such that $u_i$ and $w_j$ are connected if and only if $v_i$ and $v_j$ would be connected in the original graph in order to turn it (the original graph) into a $\Delta$-regular graph.

However, I cannot figure out how to do it in the general case where, for instance, the order of $G$ may be even or odd (and, thus, may not be made into an $r$-regular graph if r is odd as well) or for when $r>\Delta$. (I am also having trouble with the just language of graph theory and how to write proofs for it if you couldn't tell.)

Answer 1

Use induction on $r-\delta$, where $\delta=\delta(G)$ is the smallest degree of any vertex in $G$.

If $r-\delta=0$, then you are done.

If $r-\delta > 0$ then create two disjoint copies of $G$, say $G_1$ and $G_2$. For any vertex $v$ in $G$ of degree less than $r$, add an edge between the corresponding vertices $v_1$ in $G_1$, $v_2$ in $G_2$. Call the resulting graph $G'$. Then $G'$ contains $G$ as an induced subgraph, and $r-\delta(G')=r-\delta(G)-1$.

Answer 2

You can construct the graph explicitly as well, although the one I describe is much larger than the one you get from the Gale-Ryser technique.

Take your input graph $G$ with maximum degree $\Delta$ and a number $r \geq \Delta$.

Create $(r+1)!$ copies of $G$. For each vertex $v_i \in V(G)$, let $d_i$ be the degree of $v_i$ in $G$. Partition the $(r+1)!$ copies of $G$ into parts of size $r-d_i+1$ (which divides $(r+1)!$). For each part, connect all copies of $v_i$ with edges. This increases the degree at each $v_i$ from $d_i$ by $r-d_i$ to $r$.

Answer 3

Take two copies $G_1$ and $G_2$ of $G$ and add and edge between each vertex $v$ of $G_1$ and every vertex of $G_2$ corresponding to non-neighbours of $v$. Then $G$ is obviously an induced subgraph, the obtained graph is $|G|-1$ regular and has order $2|G|$.

Answer 4

Here's a silly group-theoretic proof.

Fix a free group F of suitably large rank, and realise it as the fundamental group of a rose R. Label and orient G so that there is an immersion G->R. Then G corresponds to a subgroup H of F. Let n be the diameter of G, and consider the finite set S of all elements of F of length at most n+1 that are not contained in H. By Marshall Hall's Theorem, G embeds in a finite cover R' of R such that no non-trivial elements of S are contained in the subgroup corresponding to R'.

Now, R' is regular, and G is an induced subgraph. Indeed, it is a subgraph by construction, and if it were not induced then there would be two non-adjacent vertices of G joined by an arc in R'. But this corresponds to a loop in R' of length at most n+1 that does not correspond to an element of H, which we have ruled out by construction.

(In the above, I've been a little sloppy about what I mean by length. One really needs to consider all conjugates of such elements by short words, so perhaps S needs to be a little bigger. But the idea works.)

Answer 5

Let $k = 2 \lceil {r \over 2} \rceil$ and start with $G_k = k \cdot G$ such that we have $k$ copies of $G$ and, thus, $k$ copies of each vertex $v_i \in V(G)$. Next, partition $G_k$ into $n=|G|$ subsets $G_1,...,G_n$ such that each consists of the $k$ copies of vertex $v_i \in V(G)$. Each element in a given subset has degree $d_i \leq r $ and is adjacent to no other element in the subset, thus, we can form a $(r-d_i)$-regular subgraph amongst the vertices in a particular subset. We know this is possible because each subset has an even number of elements ($k$ was defined to be even). Performing this for all subsets $G_1,...,G_n$ will result in an r-regular graph $G_k$ of order $kn$. Finally, since all of the added edges run only between copies of the same vertex, any subset of $V(G_k)$ corresponding to one of the $k$ copies of $V(G)$ will induce the original graph $G$.

Answer 6

In that case, the answer is given by Classification of degree (bi-)sequences of bipartite graphs? You call the vertices of your graph red, and you want to have a collection of blue vertices, so that the degree of every red vertex $v_i$ equals $r-d_i,$ where $d_i$ is the degree of $v_i$ in your graph $G.$ The degrees of the blue vertices are unspecified. The Gale-Ryser theorem (mentioned in the question cited above) tells you that this can be done.

EDIT Here is a better way: join every vertex $v_i$ to $r - d_i$ new vertices. When we are done, we have added $K=r n - \sum_i d_i$ new vertices. All of the old vertices now have degree $r,$ so we leave them be. The new vertices all have degree $1.$ If there exists a graph on $K$ vertices of degree $r-1,$ draw the edges of that graph between the corresponding new vertices, and we are done. If there is not such a graph, that means that either $K$ has the wrong parity, or is too small, but this is easy to fix by adding a few newer vertices (it is clear that we will never need to add more than $2r$ extra vertices, the precise bound is an exercise to the reader).