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

  • #1

Homework Statement



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

Homework Equations



NA

The Attempt at a Solution



I can picture the answer for when G itself could 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 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 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.)
 

Answers and Replies

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

Replies
2
Views
6K
Replies
0
Views
1K
  • Last Post
Replies
6
Views
8K
Replies
0
Views
4K
Replies
6
Views
1K
  • Last Post
Replies
4
Views
1K
Replies
1
Views
2K
Replies
2
Views
1K
Top