I'm given a problem statement which states "There always exists a vertex from a tree G such that the remaining connected components have size at most |V(G)|/2".

I'm trying to formulate an efficient algorithm for this and am not sure where to start. I'd love some hints and can take it from there. Thanks.

  • $\begingroup$ We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Sep 17, 2019 at 21:35
  • $\begingroup$ The first step is proving that such a vertex always exists. Perhaps the proof will give you some ideas. $\endgroup$ Sep 17, 2019 at 22:01
  • $\begingroup$ Also see math.stackexchange.com/questions/1742440/… $\endgroup$
    – xskxzr
    Sep 18, 2019 at 6:04


Browse other questions tagged or ask your own question.