Hey chocaholic, I'm puzzled by the exact same thing. I take it you're doing APM 3707 through UNISA?
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.
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