(a) Let T be a tree with vertices of degree 1 and 3 only. If T has 10 vertices of degree 3, how many vertices does it have of degree 1?
(b) Let G be a connected graph with n vertices and n edges. How many cycles does G have?
(c) How many leaves in a complete 3-ary tree with 10 internal nodes?
could someone explain to me how to do those plz. thanks!
b)A tree has n-1 edges. So there can only be one cycle in a graph with one more edge than that of a tree.
Originally Posted by melody
c)At each level of the tree you are tripling the number of nodes you have. But the tree is not complete. You can make a complete tree up till the 9th level and then count the remaining nodes as they are. The upper nodes will form a diverging geometric series with common ratio equal to 3.