Results 1 to 3 of 3

Math Help - Applied combinatorics: graph theory non-isomorphic trees help please?

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    54

    Applied combinatorics: graph theory non-isomorphic trees help please?

    Hi I wonder if someone can help me with the following questions:

    (a) List all non-isomorphic trees (not rooted) on 12 vertices with each vertex of degree either 1 or 3.
    I get only one such tree with 5 internal vertices of degree 3 and 7 leaves (of degree 1) I think this is correct but if I'm missing something please let me know.
    The question I'm having trouble with is this one:

    (b)Explain why your list in (a) contains no repetition (i.e. why the trees are all non-isomorphic), as well as why your list contains all such trees.

    I used trial and error to find the tree so how do explain that it is unique?

    Any help would be greatly appreciated.

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Feb 2010
    Posts
    40
    Hey chocaholic, I'm puzzled by the exact same thing. I take it you're doing APM 3707 through UNISA?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    54
    Hi
    I'm actually doing MAT3707- Applied combinatorics through UNISA. I ended up drawing 2 non-isomorphic trees and using the explanation that one was branched and the other was not. As to why all such trees were included I used the fact that a tree on n vertices has n-1 edges and the total degree of the tree is equal to twice the number of edges since all vertices had to be either degree 1 or 3 we have 3n1+n2=22 then I showed that its only possible for n1=5 and n2=7 as any other combination violated the degree requirements. I don't know how sound my reasoning is though. Hope this helps
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory - Trees and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 10th 2010, 12:14 AM
  2. Graph Theory question about trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 03:52 AM
  3. Graph Theory question about trees
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 26th 2009, 04:30 PM
  4. Graph theory: Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2009, 01:30 PM
  5. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2007, 01:29 AM

Search Tags


/mathhelpforum @mathhelpforum