1 votes 1 votes 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 asked Sep 18, 2018 edited Nov 19, 2019 by Lakshman Bhaiya go_editor 547 views answer comment Share Follow See 1 comment See all 1 1 comment reply Shiva Sagar Rao commented May 7, 2021 reply Follow Share For (i): https://gateoverflow.in/124367/isi-entrance-exam-mtech-cs 0 votes 0 votes Please log in or register to add a comment.
0 votes 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 See all 3 3 Comments reply Soumya95 commented Apr 19, 2020 reply Follow Share 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 votes 0 votes Falahamin commented May 4, 2020 reply Follow Share yes you are correct,i took the definition for degree of node in a graph.maybe a complete binary tree is the solution 0 votes 0 votes Priyansh Singh commented Jun 28, 2020 reply Follow Share k = n-2 . 0 votes 0 votes Please log in or register to add a comment.