# [SOLVED] Graph Theory Question - Totally stumped

• May 12th 2010, 07:46 PM
MathHelp12345
[SOLVED] Graph Theory Question - Totally stumped
Hey guys,

I'm working on a Discrete Math assignment and I came across a graph theory question that has me thinking "what?!" I would appreciate some help getting the answer. It might be easy, but I just can't think of it.

Question:

There are ________ non-isomorphic rooted trees with five vertices.

Any and all help is greatly appreciated!

Thanks guys and gals!
• May 12th 2010, 09:08 PM
undefined
Quote:

Originally Posted by MathHelp12345
Hey guys,

I'm working on a Discrete Math assignment and I came across a graph theory question that has be thinking "what?!" I would appreciate some help getting the answer. It might be easy, but I just can't think of it.

Question:

There are ________ non-isomorphic rooted trees with five vertices.

Any and all help is greatly appreciated!

Thanks guys and gals!

Maybe you're confused by the non-isomorphic part. It means, how many rooted trees with five vertices exist that are distinct up to isomorphism? So, just try to draw them all.

Edit: Actually, there seem to be quite a few, but I think you can count them without enumerating them by dividing into subtrees.

Edit 2: I had accidentally started drawing trees with 6 vertices and overestimated the count. 5 isn't too bad.
• May 12th 2010, 09:44 PM
MathHelp12345
Quote:

Originally Posted by undefined
Maybe you're confused by the non-isomorphic part. It means, how many rooted trees with five vertices exist that are distinct up to isomorphism? So, just try to draw them all.

Edit: Actually, there seem to be quite a few, but I think you can count them without enumerating them by dividing into subtrees.

Edit 2: I had accidentally started drawing trees with 6 vertices and overestimated the count. 5 isn't too bad.

Thanks for the help! So what you're saying it's just asking how many ways can a tree with 5 vertices be drawn? If so, I'm assuming there is a formula for this, and not just the brute force method. Do you, or anyone else know what this formula might?

EDIT: Okay so I looked around and I think I found the answer, but I'm not entirely sure. The non-isomorphic part is still throwing me off a little bit. If i'm looking at this question correctly for 3 vertices the answer would be 5, the answer for 4 vertices would be 14, and for the 5 vertices question the answer would be 42?

However! Would non-isomorphic mean the same thing as "structurally different"? In that case the answer for 5 vertices would be 6, correct?

EDIT 2: Actually, I'm now quite certain the answer is 3.
• May 12th 2010, 10:07 PM
undefined
Quote:

Originally Posted by MathHelp12345
Thanks for the help! So what you're saying it's just asking how many ways can a tree with 5 vertices be drawn? If so, I'm assuming there is a formula for this, and not just the brute force method. Do you, or anyone else know what this formula might?

EDIT: Okay so I looked around and I think I found the answer, but I'm not entirely sure. The non-isomorphic part is still throwing me off a little bit. If i'm looking at this question correctly for 3 vertices the answer would be 5, the answer for 4 vertices would be 14, and for the 5 vertices question the answer would be 42?

However! Would non-isomorphic mean the same thing as "structurally different"? In that case the answer for 5 vertices would be 6, correct?

EDIT 2: Actually, I'm now quite certain the answer is 3.

I'm not sure what you're counting, but I got 9, and I confirmed my answer with OEIS, sequence A000081.

If you'd like me upload an image, I can make one, just post a reply.
• May 12th 2010, 10:18 PM
MathHelp12345
Quote:

Originally Posted by undefined
I'm not sure what you're counting, but I got 9, and I confirmed my answer with OEIS, sequence A000081.

If you'd like me upload an image, I can make one, just post a reply.

I've been looking it up on various sites and everywhere seems to think the answer is 3. A non-isomorphic tree is a tree that is totally different, meaning it is not the same tree just drawn a different way.

Thus the answer should be, if I'm doing it correctly:

--*--*--*--*--*

*
|
--*--*--*
|
*

*
|
*--*--*
|
*

This last one cannot be drawn right because it wont let me add spaces, but the two edges leading up and down at the beginning should be over the middle V

Sorry for the poorly drawn trees but '*' is a vertex and '--' is an edge.

http://www.maths.usyd.edu.au/u/sandr...009/t04sol.pdf

EDIT: Now that I think about it these trees aren't rooted. 9 very well may be the answer, could you show me a picture of that please?
• May 12th 2010, 10:36 PM
undefined
Quote:

Originally Posted by MathHelp12345
I've been looking it up on various sites and everywhere seems to think the answer is 3. A non-isomorphic tree is a tree that is totally different, meaning it is not the same tree just drawn a different way.

Thus the answer should be, if I'm doing it correctly:

--*--*--*--*--*

*
|
--*--*--*
|
*

*
|
*--*--*
|
*

This last one cannot be drawn right because it wont let me add spaces, but the two edges leading up and down at the beginning should be over the middle V

Sorry for the poorly drawn trees but '*' is a vertex and '--' is an edge.

http://www.maths.usyd.edu.au/u/sandr...009/t04sol.pdf

Keep in mind we are dealing with rooted trees. And a way to enter in text with spaces is to enclose the text in [ code][ /code] tags (without spaces).

Here's a diagram

http://i43.tinypic.com/mt41gk.png

(a bit ugly since I made it in MS Paint w/ a mouse - but don't knock it because it took some time to make!)

On the second line I demonstrate what isomorphic equivalence refers to, using the $\displaystyle \equiv$ symbol to indicate equivalence.

Note how the last graph on the third line and the last graph on the last line would be equivalent if we were dealing with non-rooted trees... but we're not.
• May 12th 2010, 10:38 PM
MathHelp12345
Quote:

Originally Posted by undefined
Keep in mind we are dealing with rooted trees. And a way to enter in text with spaces is to enclose the text in [ code][ /code] tags (without spaces).

Here's a diagram

http://i43.tinypic.com/mt41gk.png

(a bit ugly since I made it in MS Paint w/ a mouse - but don't knock it because it took some time to make!)

On the second line I demonstrate what isomorphic equivalence refers to, using the $\displaystyle \equiv$ symbol to indicate equivalence.

Note how the last graph on the third line and the last graph on the last line would be equivalent if we were dealing with non-rooted trees... but we're not.

Thank you! About two seconds ago it just occurred to me that those trees aren't rooted! I edited my previous post, but I did it at about the same time you posted this.