# Graph Theory homework help

• Nov 10th 2009, 09:29 AM
signature
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
• Nov 10th 2009, 12:04 PM
Opalg
Quote:

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.)
• Nov 14th 2009, 04:16 AM
signature
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.
• Nov 14th 2009, 12:23 PM
emakarov
Quote:

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.
• Nov 17th 2009, 11:15 AM
signature
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
• Nov 17th 2009, 02:34 PM
emakarov
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.