The question goes like this:
"Let G be a 9-regular graph with p vertices and suppose G has the property that any subgraph with more than 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 are removed from G, then what remains is a graph with more than |V(H)| + 1 components of odd order."
I don't have the slightest idea on where and how to start thinking about solving this.
Can someone please help with some pointers?
"Let G be a 9-regular graph with p vertices and suppose G has the property that any subgraph with more than 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 are removed from G, then what remains is a graph with more than |V(H)| + 1 components of odd order."
I don't have the slightest idea on where and how to start thinking about solving this.
Can someone please help with some pointers?