# Thread: Graph Theory homework help

1. ## Graph Theory homework help

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

2. Originally Posted by signature
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:
Code:
o
|
o – o – o
/ \
o   o
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.)

3. ## How to prove isomorphism on trees

Thanks, i have found all the trees on 6 vertices up to isomorphism.

I have got 6 different trees.

How can i prove there there is no other trees.

4. Thanks, i have found all the trees on 6 vertices up to isomorphism... How can i prove there there is no other trees.
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 is
Code:
o
|
o-o-o-o
|
o
It is left to show that there are exactly 3 trees where the highest vertex degree is 3.

5. ## Proving isomorphism on trees

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

6. Nothing else comes to mind.

The enumeration method is not as neat, but it can be completely strict. You just have to make sure that your cases are exhaustive.