• Register
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
  • Questions
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Unanswered
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Tags
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Categories
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Users
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exams Taken
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exam List
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

DM-Graphs-Q4


Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+3 votes

A certain tree of order n has only vertices of degree 1 and degree 3. How many degree-3 vertices does the tree have?

(A). \frac{n-1}{2}

(B). \frac{n-2}{2}

(C). \frac{n}{2}

(D). \frac{n-1}{3}

asked Jul 12, 2019 by gbeditor-2 (72,840 points) 1 flag
reshown Jul 13, 2019 by gbeditor-2

2 Answers

+1 vote
Ans is B.

I solved by taking counter examples

for n = 4 no of 3 degree vertex = 1

for n = 8 no of 3 degree vertex  = 3.
answered Jul 13, 2019 by (450 points)
an order of a tree and of a b-tree means the same?
No, we can not take a Binary tree here. Because if we take Binary tree then at least one vertex should have degree 2, which is not allowed.
So, here we should take the ternary tree.
I didn't mean binary tree @lakshmanpro20, I meant B-tree
https://en.wikipedia.org/wiki/B-tree

Actually, I am confused about the term order of the tree is 'n'  what does that mean?
Yes, we can take B-tree. Because here order is given.
order represents no of vertices.
I am getting answer as (n-1)/3 when I take random values of n with deg 1 and deg 3 vertices
you are doing the mistake of taking degree 4 as 3. for example
       .
     / | \
    .
  / | \
here only the top most element has degree 3, bottom left vertex has degree 4 if you see carefully. I was doing the same mistake initially and I also got option D by taking random cases.
+1 vote
(n-b)1 + 3b=2(n-1)[2*no. of edges in tree]

slove for b.

NOTE: edges in tree = n-1
answered Jan 2, 2020 by rajatmaheshwari2572one (8,040 points)
Answer:

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
...