Let G be a 9-regular graph with p vertices and suppose G has the property that any subgraph with more that 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 17th 2008, 02:23 AM
We must be in the same class. Have you worked out the answer yet? I've been working on it all day without any luck.
Oct 19th 2008, 04:59 AM
it looks like everyone is having trouble doing this assignment (Doh)
have u guys worked out the answer yet？
Oct 19th 2008, 05:04 AM
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?
Oct 20th 2008, 12:17 AM
I'm pretty much screwed. Going to have another crack Tuesday night...