Results 1 to 2 of 2

Thread: Spanning Trees

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    30

    Spanning Trees

    For $\displaystyle n \geq 2 $ , let u be a fixed vertex of the complete graph $\displaystyle K_{n} $. Compute the number $\displaystyle \tau_{u}(n) $ of spanning trees of $\displaystyle 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 $\displaystyle 1/e $ where $\displaystyle 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 $\displaystyle f_n(d_1,...,d_n) $ the number of labeled ( label set $\displaystyle \{1,...,n\}$ ) trees - with n vertices- such that the degree of vertex $\displaystyle i$ is $\displaystyle d_i$.

    Then we have the generating function: $\displaystyle 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}$ $\displaystyle (*)$

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

    But of course if we require the exponent of $\displaystyle x_u$ to be one we have the generating function: $\displaystyle 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 $\displaystyle x_u$ in one of the $\displaystyle (x_1+x_2+...+x_n)$ we had in $\displaystyle F$.

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

    And the total number of labelled trees is .

    $\displaystyle (*)$ 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: Feb 26th 2011, 10:33 AM
  2. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 15
    Last Post: Nov 5th 2010, 06:02 AM
  3. Spanning Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 27th 2010, 04:07 PM
  4. Spanning trees
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 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