Results 1 to 3 of 3

Math Help - Trees problem

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    11

    Question 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by melody View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    4
    Quote Originally Posted by melody View Post
    (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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trees?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 13th 2010, 05:27 PM
  2. One More Trees Problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 4th 2009, 07:54 AM
  3. how can you plant 10 trees in 5 rows of 4 trees each?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2008, 12:43 PM
  4. Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 6th 2008, 09:24 PM
  5. Trees
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 6th 2008, 04:27 PM

Search Tags


/mathhelpforum @mathhelpforum