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.
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 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.
From the other thread:
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"?