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

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

2011-01-17T16:44:17Z

How would you prove that every graph G is an induced subgraph of an r-regular graph where r >= D and D is the largest degree of the vertices of G?

I can picture the answer for when G itself can be turned into a D-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 D-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 > D. (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 by GraphTheoryHurtsMyBrain for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-17T17:33:00Z

@igor: Any r >= D

Answer by Igor Rivin for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-17T19:04:50Z

In that case, the answer is given by http://mathoverflow.net/questions/48702 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).

Answer by Derrick Stolee for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-17T19:34:37Z

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 by HW for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-17T19:53:21Z

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 by AnotherStudent for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-18T01:07:40Z

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 by Louigi Addario-Berry for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-18T03:12:18Z

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 by Patrice Ossona de Mendez for Proving that every graph is an induced subgraph of an r-regular graph

2011-08-08T08:22:45Z

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