Results 1 to 14 of 14

Math Help - Help with trees

  1. #1
    Member
    Joined
    Oct 2006
    Posts
    84

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by clockingly View Post
    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.
    Attached Thumbnails Attached Thumbnails Help with trees-picture3.gif  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2006
    Posts
    84
    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.
    Last edited by clockingly; October 29th 2006 at 09:45 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by clockingly View Post
    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
    Last edited by Quick; October 31st 2006 at 01:24 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2006
    Posts
    84
    thank you so much!

    that really helped!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by ThePerfectHacker View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by ThePerfectHacker View Post
    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...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2006
    Posts
    84
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Quick's Avatar
    Joined
    May 2006
    From
    New England
    Posts
    1,024
    Quote Originally Posted by clockingly View Post
    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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by clockingly View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Oct 2006
    Posts
    84
    doesn't "isomorphic" just mean that the graphs have the same number of edges and vertices, though?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by clockingly View Post
    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:
    G=(V,E) und G'=(V',E')
    They are isomorphic means that,
    There exists a bijection,
    \phi:V\to V and \phi(ab)=\phi(a)\phi(b)
    And,
    \forall xy\in E' \exists a,b\in V such that xy=\phi(a)\phi(b)
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Oct 2006
    Posts
    84
    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?
    Last edited by clockingly; October 29th 2006 at 12:15 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How Many Trees?
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: September 12th 2010, 10:52 PM
  2. Trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 21st 2009, 01:00 PM
  3. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2008, 12:43 PM
  4. Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 6th 2008, 09:24 PM
  5. trees
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 22nd 2007, 10:22 AM

Search Tags


/mathhelpforum @mathhelpforum