Thread: [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!

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.

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.

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.

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?

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



(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 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.

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



(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 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.

9 is the answer.

Thanks for the help!