Proving that every graph is an induced subgraph of an r-regular graph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T21:05:09Z http://mathoverflow.net/feeds/question/52333 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph Proving that every graph is an induced subgraph of an r-regular graph GraphTheoryHurtsMyBrain 2011-01-17T16:44:17Z 2011-08-08T08:22:45Z <p>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?</p> <p>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.</p> <p>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.) </p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52335#52335 Answer by GraphTheoryHurtsMyBrain for Proving that every graph is an induced subgraph of an r-regular graph GraphTheoryHurtsMyBrain 2011-01-17T17:33:00Z 2011-01-17T17:33:00Z <p>@igor: Any r >= D</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52342#52342 Answer by Igor Rivin for Proving that every graph is an induced subgraph of an r-regular graph Igor Rivin 2011-01-17T19:04:50Z 2011-01-18T03:38:15Z <p>In that case, the answer is given by <a href="http://mathoverflow.net/questions/48702" rel="nofollow">http://mathoverflow.net/questions/48702</a> You call the vertices of your graph <em>red</em>, 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.</p> <p><strong>EDIT</strong> 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).</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52345#52345 Answer by Derrick Stolee for Proving that every graph is an induced subgraph of an r-regular graph Derrick Stolee 2011-01-17T19:34:37Z 2011-01-17T19:34:37Z <p>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.</p> <p>Take your input graph $G$ with maximum degree $\Delta$ and a number $r \geq \Delta$.</p> <p>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$.</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52347#52347 Answer by HW for Proving that every graph is an induced subgraph of an r-regular graph HW 2011-01-17T19:53:21Z 2011-01-17T19:53:21Z <p>Here's a silly group-theoretic proof.</p> <p>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'.</p> <p>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.</p> <p>(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.)</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52367#52367 Answer by AnotherStudent for Proving that every graph is an induced subgraph of an r-regular graph AnotherStudent 2011-01-18T01:07:40Z 2011-01-18T01:14:09Z <p>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$.</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52375#52375 Answer by Louigi Addario-Berry for Proving that every graph is an induced subgraph of an r-regular graph Louigi Addario-Berry 2011-01-18T03:12:18Z 2011-01-18T03:12:18Z <p>Use induction on $r-\delta$, where $\delta=\delta(G)$ is the smallest degree of any vertex in $G$. </p> <p>If $r-\delta=0$, then you are done. </p> <p>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$.</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/72336#72336 Answer by Patrice Ossona de Mendez for Proving that every graph is an induced subgraph of an r-regular graph Patrice Ossona de Mendez 2011-08-08T08:22:45Z 2011-08-08T08:22:45Z <p>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|$. </p>