1. ## 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.

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

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

how do i find the complements of those? reason i'm confused is because i didn't draw them in the pentagon shape.

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

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

5. thank you so much!

that really helped!

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

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

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

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

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

11. 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?

12. doesn't "isomorphic" just mean that the graphs have the same number of edges and vertices, though?

13. 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)$

14. 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?