Results 1 to 3 of 3

Math Help - Graph Theory Problem #2

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Graph Theory Problem #2

    Prove that every tree with maximum degree x has at least x leaves.

    Any thoughts? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    For each edge incident to a vertex with maximum degree, proceed along any path starting with that vertex and edge. The path has to end somewhere without looping back, as the graph is acyclic. Thus we have a leaf for each such path.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    2
    Quote Originally Posted by jzellt View Post
    Prove that every tree with maximum degree x has at least x leaves.

    Any thoughts? Thanks.
    Let v be vertex of degree x . Every maximal paths starts from v will end with leaf. No two such path intersects since tree has no cycle . Therefore tree has atleast x leaves
    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, 03:29 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 09:36 PM
  3. Graph Theory Problem
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: September 15th 2010, 01:40 AM
  4. Help with Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2008, 11:08 PM
  5. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 26th 2007, 12:56 PM

Search Tags


/mathhelpforum @mathhelpforum