# Help with trees

• Oct 29th 2006, 06:56 AM
clockingly
Help with trees
ok, so i'm supposed to draw all the trees with five vertices and their complements. now, i have all the trees with five vertices down. but i don't know how to draw their complements. can anyone help me with this and show me an example of one? i would be really grateful.
• Oct 29th 2006, 07:04 AM
ThePerfectHacker
Quote:

Originally Posted by clockingly
ok, so i'm supposed to draw all the trees with five vertices and their complements. now, i have all the trees with five vertices down. but i don't know how to draw their complements. can anyone help me with this and show me an example of one? i would be really grateful.

To find a complement you need to subtract from the complete graph on 5 vertices.

Below is the tree on 5 vertices and its complemnt in red.
• Oct 29th 2006, 08:26 AM
clockingly
thanks! sorry about my other post in the urgent forum. i didn't know it wasn't allowed.

i'm still confused, though.

the picture you uploaded is a graph. but i'm supposed to be drawing the complement of a tree (unless the one you uploaded is also a tree??). all the trees with five vertices are at the link below.

http://f3.yahoofs.com/users/41a9d7b5...ozORFBGFWDAkwy

how do i find the complements of those? reason i'm confused is because i didn't draw them in the pentagon shape.
• Oct 29th 2006, 08:49 AM
Quick
Quote:

Originally Posted by clockingly
thanks! i'm still confused, though.

the picture you uploaded is a graph. but i'm supposed to be drawing the complement of a tree (unless the one you uploaded is also a tree??). all the trees with five vertices are at the link below.

http://f3.yahoofs.com/users/41a9d7b5...ozORFBGFWDAkwy

how do i find the complements of those?

[draw=100]Point (20,20); Point (40,20); Point (60,20); Point (80,20); Point (60,40); Segment (1,2); Segment (3,5); Segment (2,3); Segment (3,4);[/draw]

That is the tree ----->

[draw=100]Point (20,20); Point (40,20); Point (60,20); Point (80,20); Point (60,40); Segment (1,5); Segment (2,5); Segment (4,5);[/draw]

That is the complement. ---->

[EDIT] apparently not :(
• Oct 29th 2006, 08:51 AM
clockingly
thank you so much!

that really helped!
• Oct 29th 2006, 08:58 AM
ThePerfectHacker
Nice visuals Quick but I do not think that is the answer. First the number of edges need to be six.
And the complement of a connected graph is a connected graph.
• Oct 29th 2006, 09:02 AM
Quick
Quote:

Originally Posted by ThePerfectHacker
Nice visuals Quick but I do not think that is the answer. First the number of edges need to be six.
And the complement of a connected graph is a connected graph.

Oh, well then nevermind...

You're going to have to explain the idea more clearly...
• Oct 29th 2006, 09:12 AM
Quick
Quote:

Originally Posted by ThePerfectHacker
Nice visuals Quick but I do not think that is the answer. First the number of edges need to be six.
And the complement of a connected graph is a connected graph.

really? looking at wikipedia it says that all you do is connect the unconnected vertices...
• Oct 29th 2006, 09:20 AM
clockingly
hey Quick -

so if your method is right and if i'm correct, then aren't both the last tree and its complement isomorphic?

the last tree would look like a vertex in the middle (not connected to anything) with its four surrounding points connected in a diamond shape i think.
• Oct 29th 2006, 09:25 AM
Quick
Quote:

Originally Posted by clockingly
hey Quick -

so if your method is right and if i'm correct, then aren't both the last tree and its complement isomorphic?

You're going to have to wait for a response from someone who's more "intune" with graphs, as all I know right now are circuits and paths :(
• Oct 29th 2006, 09:28 AM
ThePerfectHacker
Quote:

Originally Posted by clockingly
hey Quick -

so if your method is right and if i'm correct, then aren't both the last tree and its complement isomorphic?

the last tree would look like a vertex in the middle (not connected to anything) with its four surrounding points connected in a diamond shape i think.

First I do not think that is correct (though I am not expert on Graph theory). Because the complement is not connected while the original graph is connected. So how can they be isomorphic?
• Oct 29th 2006, 09:30 AM
clockingly
doesn't "isomorphic" just mean that the graphs have the same number of edges and vertices, though?
• Oct 29th 2006, 09:45 AM
ThePerfectHacker
Quote:

Originally Posted by clockingly
doesn't "isomorphic" just mean that the graphs have the same number of edges and vertices, though?

No, if two graphs are isomorphic then it means they have the same number of edges and vertices but not the other say around.

Formally, given two graphs:
$\displaystyle G=(V,E)$ und $\displaystyle G'=(V',E')$
They are isomorphic means that,
There exists a bijection,
$\displaystyle \phi:V\to V$ and $\displaystyle \phi(ab)=\phi(a)\phi(b)$
And,
$\displaystyle \forall xy\in E' \exists a,b\in V$ such that $\displaystyle xy=\phi(a)\phi(b)$
• Oct 29th 2006, 10:22 AM
clockingly
ok, so i get that the degrees of each vertice has to be the same in both graphs.

i'm also confused because i'm supposed to find all the trees that are isomorphic to their complements. how do i approach this? aren't there infinitely many trees?