Results 1 to 5 of 5

Math Help - subgraph

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    13

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2008
    Posts
    6
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12
    it looks like everyone is having trouble doing this assignment
    have u guys worked out the answer yet?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    6
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2008
    Posts
    13
    I'm pretty much screwed. Going to have another crack Tuesday night...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Spanning Subgraph
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 22nd 2011, 12:54 AM
  2. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 6th 2011, 05:13 PM
  3. how many subgraph...
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 07:03 AM
  4. Subgraph Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 8th 2008, 12:33 PM

Search Tags


/mathhelpforum @mathhelpforum