1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory proof (Unlabeled trees)

  1. Jan 19, 2016 #1
    1. The problem statement, all variables and given/known data
    A. Show that n^n−2/n! < T(n) by looking at how the symmetric group Sn acts on labelled trees. Use |Sn| = n!
    T(n) is the number of unlabeled trees on n vertices

    2. Relevant equations


    3. The attempt at a solution
    I can't find any mathematical relation between labelled trees and unlabeled trees. I drew the non isomorphic graphs on different number of vertices. For example on 5 vertices, there are 3 non isomorphic classes. I counted the number of different trees on each class by hand. I just could notice that I always use the n!. For example the simplest class of a tree on 5 vertices is a straight line with 5 nodes. To count the number of trees you do 5!/2 because of the symmetry of this class. In this case n=5, so my point is that you always use n!.
    n^(n-2)=n!/k+n!/y+....... n!/z

    The number of terms depends on the number of vertices, but I don't know how.

    I thought that I could do something like this (n!/k+n!/y+....n!/z)/n!= 1/k+1/y+1/z and find something meaningful in the constants but turns out I couldn't.
     
  2. jcsd
  3. Jan 19, 2016 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Not even an inequality?
    If you take an unlabelled tree and label it, what is the greatest number of distinct labelled trees you might produced?
     
  4. Jan 19, 2016 #3
    I found the different unlabeled trees. As I was saying, there are 3 classes of unlabeled trees on 5 vertices. In the first class, a straight line, we can't use the n! because this generates duplicates. I know that the greatest number of labeled trees on n vertices y n^(n-2), but counting the number of labelled trees from a unlabeled tree is a tough task.

    http://mathworld.wolfram.com/Tree.html

    My point can be explained better with this picture. Each class on different n vertices is drawn and I am attempting to count each one of them by hand and find some meaningful relation.
     
  5. Jan 19, 2016 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, but I'm not asking for the precise number, just an upper bound. How many ways could you assign the labels? Could there be some you've missed?
     
  6. Jan 19, 2016 #5
    n vertices would be n!
     
  7. Jan 19, 2016 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Right. Could there be any labelled trees missed by this procedure (generating n! labellings from each unlabelled tree)?
     
  8. Jan 19, 2016 #7
    no intuitively n!>n^(n-2), the last thing I said is wrong, the answer is no. If we apply n! on each unlabeled tree, we miss nothing.
     
  9. Jan 19, 2016 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Eh? Not true.
    Right. So what inequality can you write relating the number labelled trees on n vertices to the number of unlabelled trees on n vertices?
     
  10. Jan 19, 2016 #9
    n!>unlabeled trees?? I don't know. I need more clues.
     
  11. Jan 19, 2016 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Applying all n! possible labellings to every possible unlabelled tree we found every possible labelled tree (though perhaps with repeats). What relationship does that yield between the total number of unlabelled trees and the total number of labelled trees?
     
  12. Jan 19, 2016 #11
    if we sum all the n!, we would get something like kn!>n^(n-2) where k is the possible number of unlabeled trees ohhhhhh xd k>n^(n-2)/n!. right?
     
  13. Jan 19, 2016 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Bingo.
     
  14. Jan 19, 2016 #13
    thank you so much sir!!!!!!! really thank you.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Graph theory proof (Unlabeled trees)
  1. Graph Theory Proof (Replies: 1)

  2. Graph theory proof (Replies: 11)

  3. Graph theory proof (Replies: 22)

  4. Graph theory proof (Replies: 4)

Loading...