Results 1 to 5 of 5

Math Help - please help~~graph theory problem

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12

    please help~~graph theory problem

    Let G be a 9-regular graph with p vertices and suppose G has the property that
    any subgraph with more that p/21 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.
    Follow Math Help Forum on Facebook and Google+

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

  3. #3
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12
    yeh, we must be in the same class
    have u worked out the answer yet?
    it took me the whole to work on Q1, still don't know what's going on~~~
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    From
    australia
    Posts
    12
    Quote Originally Posted by TomP View Post
    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.
    yeh, we must be in the same class
    have u worked out the answer yet?
    it took me the whole to work on Q1, still don't know what's going on~~~
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2008
    Posts
    6
    From the other thread:
    Quote Originally Posted by TomP View Post
    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 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"?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 02:29 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  3. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 20th 2009, 07:50 PM
  4. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 25th 2009, 07:07 AM
  5. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 12:50 PM

Search Tags


/mathhelpforum @mathhelpforum