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

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

-
Any $r\geq D,$ or SOME $r \geq D?$ In the latter case, any graph is an induced subgroup of a complete graph... –  Igor Rivin Jan 17 '11 at 17:00
@Igor: I think there's some terminological confusion here - an induced subgraph of a complete graph is a complete graph... –  ndkrempel Jan 17 '11 at 17:25
@ndkrempel: yes, confusion reigns. –  Igor Rivin Jan 17 '11 at 17:40
Until you get 50 reputation points, you might not be able to leave comments on other people's answers; but you should be able to edit your own question, and add responses to what people have said or asked to the body of the text –  Yemon Choi Jan 17 '11 at 19:53

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

-
This is a nice recursive construction. –  Derrick Stolee Jan 18 '11 at 3:49

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

-

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

-
I suppose I can justify this answer by observing that the question asks how `you' would prove this fact. Well, this is how I would prove it. –  HJRW Jan 17 '11 at 19:54
@Henry: what kind of bound do you get on the size of this cover? Also, for us ignorami: which Marshall Hall theorem are you alluding to? –  Igor Rivin Jan 17 '11 at 20:00
That's nice, Henry. –  Richard Kent Jan 17 '11 at 22:49
Igor, first, regarding Marshall Hall's Theorem, I'm using a topological version which you can find, for instance, in Stallings's 'Topology of finite graphs'. Regarding the size of the cover, well, I can only give a rough estimate, but here goes. Let G' be the covering space of R corresponding to H. The index is equal to something like the size of the ball of radius n+1 in this covering space. Large chunks of this covering space will be trees, so this will in turn be exponential in n. One would want to be slightly more careful to calculate the constants. –  HJRW Jan 17 '11 at 23:40
... Of course, one big disadvantage of this construction is that you always get even valence. –  HJRW Jan 17 '11 at 23:41

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

-

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

-

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

-