• Oct 9th 2008, 10:25 PM
ycdfd
Let G be a 9-regular graph with p vertices and suppose G has the property that
any subgraph with more that p/21 edges has a vertex of degree 2. Prove that there is a subgraphH 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 oddorder.
• Oct 17th 2008, 03:27 AM
TomP
We're in the same class, I guess. You haven't worked out the answer yet, have you? Because I've been trying all day to no avail.
• Oct 19th 2008, 06:09 AM
ycdfd
yeh, we must be in the same class
have u worked out the answer yet?
it took me the whole to work on Q1, still don't know what's going on~~~
• Oct 19th 2008, 06:09 AM
ycdfd
Quote:

Originally Posted by TomP
We're in the same class, I guess. You haven't worked out the answer yet, have you? Because I've been trying all day to no avail.

yeh, we must be in the same class
have u worked out the answer yet?
it took me the whole to work on Q1, still don't know what's going on~~~
• Oct 19th 2008, 06:20 AM
TomP
From the other thread:
Quote:

Originally Posted by TomP
I haven't. It'd all have to do with the Introduction to Graphs section of the notes, right? I've pretty much given up on it and will have to wait til the tutorial. Question 1, anyway. Are the other two questions easier?

I think what I really need to know is how where supposed to prove it. Y'know, like do we have to prove H's property from the 9-regular/degree atleast 2 sentence? Or do we have to suppose no H with that property does exist and then find a contradiction?

Also, is "what remains is a graph with more than |V (H)| + 1 components of odd order" meant to mean all components of the graph have odd order, or that there are even ordered components in addition to the "more than |V (H)| + 1 components of odd order"?