Results 1 to 2 of 2

Math Help - Spanning Trees

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    Spanning Trees

    For  n \geq 2 , let u be a fixed vertex of the complete graph  K_{n} . Compute the number  \tau_{u}(n) of spanning trees of  K_{n} that contain the vertex u as a leaf. Use this to show that the probability a vertex in a tree on n vertices is a leaf is approximately  1/e where  e = 2.71828182... is the base number for the natural logarithm.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let's denote by f_n(d_1,...,d_n) the number of labeled ( label set \{1,...,n\} ) trees - with n vertices- such that the degree of vertex i is d_i.

    Then we have the generating function: F(x_1,..,x_n) = \sum f_n(d_1,..,d_n)\cdot x_1^{d_1}\cdot x_2^{d_2}...x_n^{d_n} = x_1\cdot ...x_n\cdot (x_1+...+x_n)^{n-2} (*)

    Now if \text{deg}(u)=1 what we want is the sum of the entries where the corresponding exponent of x_u is 1.

    But of course if we require the exponent of x_u to be one we have the generating function: R(x_1,..,x_n) = x_1\cdot ...\cdot x_n \cdot (x_1+...+x_{u-1}+x_{u+1}+...+x_n)^{n-2} since we may never choose x_u in one of the (x_1+x_2+...+x_n) we had in F.

    Thus the number of trees such that vertex u is a leaf is: R(1,...,1) = (n-1)^{n-2}

    And the total number of labelled trees is .

    (*) For further details on this read here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Spanning trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 26th 2011, 10:33 AM
  2. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: November 5th 2010, 06:02 AM
  3. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 27th 2010, 04:07 PM
  4. Spanning trees
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 27th 2010, 07:06 PM
  5. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 2nd 2009, 10:17 PM

Search Tags


/mathhelpforum @mathhelpforum