# Homework Help: Graph theory proof (Unlabeled trees)

1. Jan 19, 2016

### TheMathNoob

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. Jan 19, 2016

### haruspex

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?

3. Jan 19, 2016

### TheMathNoob

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.

4. Jan 19, 2016

### haruspex

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?

5. Jan 19, 2016

### TheMathNoob

n vertices would be n!

6. Jan 19, 2016

### haruspex

Right. Could there be any labelled trees missed by this procedure (generating n! labellings from each unlabelled tree)?

7. Jan 19, 2016

### TheMathNoob

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.

8. Jan 19, 2016

### haruspex

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?

9. Jan 19, 2016

### TheMathNoob

n!>unlabeled trees?? I don't know. I need more clues.

10. Jan 19, 2016

### haruspex

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?

11. Jan 19, 2016

### TheMathNoob

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?

12. Jan 19, 2016

### haruspex

Bingo.

13. Jan 19, 2016

### TheMathNoob

thank you so much sir!!!!!!! really thank you.