Results 1 to 5 of 5

Math Help - graphing theory proof

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    graphing theory proof

    Hey guy i am soooo stuck on this question any help would be greatly appreciated!!

    Let G be a 9-regular graph with p vertices and suppose G has the property that any subgraph with more that \frac{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)| + 1components of odd order.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Sep 2008
    Posts
    18
    Hi I am working on this as well I do not know how to appoach it? Have you started this question yet, I just don't know how to prove it? I don't really understand what they are asking in it?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    204
    Quote Originally Posted by wik_chick88 View Post
    Hey guy i am soooo stuck on this question any help would be greatly appreciated!!



    Let G be a 9-regular graph with p vertices and suppose G has the property that any subgraph with more that \frac{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)| + 1components of odd order.
    can anyone give me ANY help at all?!?!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2008
    Posts
    120
    My honours supervisor does his research in graph theory. I'll ask him for you.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    Posts
    204
    thanks that would be great i just need a start on the question or a clue anything would be so much appreciated!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with set theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 8th 2011, 11:25 AM
  2. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  3. Need help with set theory proof
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: April 6th 2010, 11:49 AM
  4. A Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 1st 2009, 03:53 PM
  5. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 13th 2006, 02:54 PM

Search Tags


/mathhelpforum @mathhelpforum