Thread: subgraph

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.

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.

it looks like everyone is having trouble doing this assignment
have u guys worked out the answer yet？

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'm pretty much screwed. Going to have another crack Tuesday night...