Thread: Trees problem

1.
(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!

Originally Posted by melody

1.
(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!

A) we know that if n is the number of vertices in G, and is a tree, then it has n-1 edges. Let v be the number of vertices of degree 1 in G.
We know that
But we also know that and

B) Try seeing what happens if you try to draw the graph with more than one circle.

Originally Posted by melody

(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.

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.