Так как в дереве нет простых циклов нечетной длины, то его можно разбить на двудольный граф.
Тогда найдется доля, в которой будет находиться хотя бы n вершин (иначе всего в графе меньше,
чем 2n вершин), причем никакие две вершины из одной доли не соединены ребром. Тогда можно
выбрать из этой доли n вершин, которые будут находиться в независимом множестве.


Заявка на расчет