Results 1 to 5 of 5

Math Help - graph theory problem

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    11

    Red face graph theory problem

    This is my problem...

    Let F be a forest with degree sequence (1,....1, 2, 3, 5, 7, 11, 13). Assuming that F has 3 components, what is the number of end vertices of F?

    I've drawn a tree with 3 components and my picture has 41 vertices. There are 6 vertices that have degree > 1. I'm certain this is true but I think there might be a formula to prove this is true but my Wilson book isn't helping me very much. If anyone has any idea, let me know. Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Some graph suggestions

    Here's 2 ways to construct a forest. Please tell me if these are legal:

    (2-3), (5-7), (11-13).
    (2-3-5), (7,11), (13).

    So what do these look like? I've attached a picture of what (2-3) represents.
    If these graphs match your criteria, I count 1 degree 1 vertex hanging off the "2" in the (2-3) graph, and 2 degree 1 vertices hanging off the "3". Continuing, I count 35 degree 1 vertices total. I get the same count in the second layout I suggested.
    Attached Thumbnails Attached Thumbnails graph theory problem-2-3.bmp  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    11

    Red face reply

    and I get 35 end vertices of degree 1 as well. and I drew two pics like what you get as well. But is a picture really justifying the answer? I'm trying to think of a proof or argument to add to show that's right.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    start of a proof?

    I applaud your desire to get a proof.

    If all 6 of the degree > 1 vertices formed it's own component, there would be 41 degree 1 vertices. We have to get rid of 3 components by combining vertices. In the course of doing so, don't we lose 1 edge per 'degree > 1' vertex? So in the first forest, we lost 2 degree 1 vertices by forming the first component, and the same for the other two. Then 41 - 3*2 = 35.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    11

    Smile hi

    That's really interesting. I didn't consider what the condition would be if it was in one component. That makes sense to me.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Problem #2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 20th 2010, 04:44 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 16th 2009, 10:33 AM
  3. Graph theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2009, 09:18 AM
  4. A graph theory problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 15th 2009, 12:08 PM
  5. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 11:08 PM

Search Tags


/mathhelpforum @mathhelpforum