# graphing theory proof

• Oct 20th 2008, 05:46 PM
wik_chick88
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 $p$ vertices and suppose $G$ has the property that any subgraph with more that $\frac{p}{2} - 1$ edges has a vertex of degree at least 2. Prove that there is a subgraph $H$ of $G$ with the property that if the vertices of $H$ and all the edges incident with the vertices of $H$ are removed from $G$, then what remains is a graph with more than $|V(H)| + 1$components of odd order.
• Oct 22nd 2008, 02:37 AM
gloiterbox
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?
• Oct 26th 2008, 09:04 PM
wik_chick88
Quote:

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 $p$ vertices and suppose $G$ has the property that any subgraph with more that $\frac{p}{2} - 1$ edges has a vertex of degree at least 2. Prove that there is a subgraph $H$ of $G$ with the property that if the vertices of $H$ and all the edges incident with the vertices of $H$ are removed from $G$, then what remains is a graph with more than $|V(H)| + 1$components of odd order.

can anyone give me ANY help at all?!?!
• Oct 27th 2008, 02:46 AM
whipflip15
My honours supervisor does his research in graph theory. I'll ask him for you.
• Oct 27th 2008, 03:36 AM
wik_chick88
thanks that would be great i just need a start on the question or a clue anything would be so much appreciated!!