1 1 vote Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than 1 in a given tree. What is the maximum possible value of $k$? Justify your answer. Consider $2n$ committees, each having at least $2n$ persons, formed from a group of $4n$ persons. Prove that there exists at least one person who belongs to at least $n$ committees. Combinatory isi2016-pcb-cs combinatory descriptive + – go_editor 1.1k views answer comment Share Follow Print See 1 comment 1 1 comment reply Shiva Sagar Rao commented May 7, 2021 reply Follow flag For (i): https://gateoverflow.in/124367/isi-entrance-exam-mtech-cs 0 0 replyShare Please log in or register to add a comment.
0 0 votes 2)https://gateoverflow.in/120576/isi-2016-pcb-c8 Falahamin answered Mar 18, 2020 • edited May 4, 2020 by Falahamin Falahamin comment Share Follow See all 3 Comments 3 3 Comments reply Soumya95 commented Apr 19, 2020 reply Follow flag If my understanding is clear, degree of a node in a tree is number of child nodes it posseses. Now, in a skewed tree, all the intermidiate nodes have degree 1. So, how can k be equal to n-1; since all the internal nodes have degree =1 and not greater than 1? 0 0 replyShare Falahamin commented May 4, 2020 reply Follow flag yes you are correct,i took the definition for degree of node in a graph.maybe a complete binary tree is the solution 0 0 replyShare Priyansh Singh commented Jun 28, 2020 reply Follow flag k = n-2 . 0 0 replyShare Please log in or register to add a comment.
