# Trees problem

• Oct 11th 2009, 05:46 PM
melody
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!
• Oct 12th 2009, 08:29 AM
Defunkt
Quote:

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 $G = (V,E)$ is a tree, then it has n-1 edges. Let v be the number of vertices of degree 1 in G.
We know that $\sum_{x \in V} deg(x) = 2|E| = 2(n-1) = 2n-2$
But we also know that $\sum_{x \in V} deg(x) = 3*10 + 1*v$ and $v = n-10 \Rightarrow 2n-2 = 30 + n-10 \Rightarrow n = 22$ $\Rightarrow v = 12$

B) Try seeing what happens if you try to draw the graph with more than one circle.
• Oct 12th 2009, 10:19 AM
hans.kruger11
Quote:

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.