Results 1 to 6 of 6

Math Help - Graph Theory homework help

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    27

    Exclamation Graph Theory homework help

    I have to find all the trees on 6 vertices up to isomorphism, and prove that there are no others.

    I am unsure of how to do this problem.

    Thanks for any help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by signature View Post
    I have to find all the trees on 6 vertices up to isomorphism, and prove that there are no others.

    I am unsure of how to do this problem.

    Thanks for any help
    One method would be to list all the possible trees systematically by looking at the highest degree of a vertex.

    If there is a vertex of degree five then the tree must look like this:
    Code:
         o
         |
     o – o – o
        / \
       o   o
    At the opposite extreme, if the highest vertex degree is two then the tree must look like this:
    Code:
      o – o – o – o – o – o
    The intermediate cases, where the highest vertex degree is three or four, take a bit more thought, but are not too hard. (Hint: there's only one possibility for the degree four case, but three different graphs in the degree three case.)
    Last edited by Opalg; November 15th 2009 at 12:37 AM. Reason: corrected error
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    27

    How to prove isomorphism on trees

    Thanks, i have found all the trees on 6 vertices up to isomorphism.

    I have got 6 different trees.

    How can i prove there there is no other trees.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Thanks, i have found all the trees on 6 vertices up to isomorphism... How can i prove there there is no other trees.
    It should follow from the systematic procedure you used to enumerate the trees. If, e.g., you consider the highest degree of a vertex, as was suggested above, then it is clear that there is only one tree for each of the degrees 1 and 5. If the highest degree is 4, then the only possibility up to isomorphism is
    Code:
      o
      |
    o-o-o-o
      |
      o
    It is left to show that there are exactly 3 trees where the highest vertex degree is 3.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    27

    Proving isomorphism on trees

    I understand the method.

    Is there anything else I could use to show to aid my proof, so i can show there any no more trees other than the 6 i obtained

    i.e. bijection, degree sequence etc.

    I have been searching the internet, but I not sure if i can use bijection, or degree sequence, as the definitions apply to graphs, wheras am dealing with trees.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Nothing else comes to mind.

    The enumeration method is not as neat, but it can be completely strict. You just have to make sure that your cases are exhaustive.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  3. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM
  5. computer theory homework
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: March 12th 2010, 05:24 AM

Search Tags


/mathhelpforum @mathhelpforum