Thread: graphing theory proof

Hey guy i am soooo stuck on this question any help would be greatly appreciated!!

Let G be a 9-regular graph with vertices and suppose has the property that any subgraph with more that edges has a vertex of degree at least 2. Prove that there is a subgraph of with the property that if the vertices of and all the edges incident with the vertices of are removed from , then what remains is a graph with more than components of odd order.

Hi I am working on this as well I do not know how to appoach it? Have you started this question yet, I just don't know how to prove it? I don't really understand what they are asking in it?

Originally Posted by wik_chick88

Hey guy i am soooo stuck on this question any help would be greatly appreciated!!

Let G be a 9-regular graph with vertices and suppose has the property that any subgraph with more that edges has a vertex of degree at least 2. Prove that there is a subgraph of with the property that if the vertices of and all the edges incident with the vertices of are removed from , then what remains is a graph with more than components of odd order.

can anyone give me ANY help at all?!?!

My honours supervisor does his research in graph theory. I'll ask him for you.

thanks that would be great i just need a start on the question or a clue anything would be so much appreciated!!