My Math Forum  

Go Back   My Math Forum > College Math Forum > Real Analysis

Real Analysis Real Analysis Math Forum

LinkBack Thread Tools Display Modes
July 29th, 2012, 07:42 AM   #1
Joined: Jul 2012

Posts: 19
Thanks: 0

Induced Subgraphs (Graph Theory)

Not sure if I am posting this in the right section.
Prove or disprove:
For every graph G and every integer , there is an r-regular graph H containing G as an induced subgraph. Thanks for any help.
Kramer is offline  
August 2nd, 2012, 09:39 AM   #2
Senior Member
Joined: Feb 2012

Posts: 628
Thanks: 1

Re: Induced Subgraphs (Graph Theory)

Can you construct an r-regular graph with an arbitrary number of vertices as long as the number of vertices exceeds a given quantity? If so, then you may construct H from G as follows: Let be the degree of the nth vertex of G. For every vertex in G with degree less than r, add a vertex to the graph and an edge connecting that vertex to and repeat this process until the degree of is r. Then you will have a graph in which the degree of the vertices originally in G is r, and the degree of the vertices not originally in G is 1. If you cannot construct an (r-1)-regular graph with the number of additional vertices (the ones not originally in G), then add two vertices and connect them with an edge. Repeat this process until you can construct an (r-1)-regular graph with the number of additional vertices. Now, for the vertices whose degree is 1, add the edges of the (r-1)-regular graph you constructed. This will complete the creation of H, and G will be an induced subgraph of H, which is seen easily by choosing the vertices originally in G, to which no edges were added in the creation of H.
icemanfan is offline  

  My Math Forum > College Math Forum > Real Analysis

graph, induced, subgraphs, theory

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
A graph problem in graph theory! lubna_mira Applied Math 0 January 12th, 2014 01:52 PM
Graph theory: Linking graph characteristics and minimal cut avnerg Applied Math 0 September 18th, 2013 06:03 AM
Graphs without induced subgraphs with 3/4 edges?! MageKnight Applied Math 0 January 15th, 2013 06:59 AM
graph theory - social networks and reverting the graph johnyjj2 Applied Math 0 December 28th, 2010 02:49 PM
Spanning and Induced Subgraphs dynas7y Applied Math 1 December 9th, 2009 06:54 AM

Copyright © 2019 My Math Forum. All rights reserved.