I have to find all the trees on 6 vertices up to isomorphism, and prove that there are no others.
I am unsure of how to do this problem.
Thanks for any help
One method would be to list all the possible trees systematically by looking at the highest degree of a vertex.
If there is a vertex of degree five then the tree must look like this:
At the opposite extreme, if the highest vertex degree is two then the tree must look like this:Code:o | o – o – o / \ o o
The intermediate cases, where the highest vertex degree is three or four, take a bit more thought, but are not too hard. (Hint: there's only one possibility for the degree four case, but three different graphs in the degree three case.)Code:o – o – o – o – o – o
It should follow from the systematic procedure you used to enumerate the trees. If, e.g., you consider the highest degree of a vertex, as was suggested above, then it is clear that there is only one tree for each of the degrees 1 and 5. If the highest degree is 4, then the only possibility up to isomorphism isThanks, i have found all the trees on 6 vertices up to isomorphism... How can i prove there there is no other trees.
It is left to show that there are exactly 3 trees where the highest vertex degree is 3.Code:o | o-o-o-o | o
I understand the method.
Is there anything else I could use to show to aid my proof, so i can show there any no more trees other than the 6 i obtained
i.e. bijection, degree sequence etc.
I have been searching the internet, but I not sure if i can use bijection, or degree sequence, as the definitions apply to graphs, wheras am dealing with trees.
Thanks