Задача
COM-B2-M07-P020 Большое независимое множество в дереве
#20
★★★★★ Уровень 5 из 5
Докажите, что в любом дереве на \(n\) вершинах есть независимое множество размера не меньше \(\lceil n/2\rceil\).
Докажите, что дерево двудольно, и возьмите большую долю.
В дереве нет циклов, значит, нет нечётных циклов. Поэтому дерево двудольно: его вершины можно разбить на две доли \(A\) и \(B\), так что каждое ребро идёт между долями.
Внутри каждой доли рёбер нет, значит, каждая доля является независимым множеством. Из двух чисел \(|A|\) и \(|B|\), сумма которых равна \(n\), одно не меньше \(\lceil n/2\rceil\). Эта большая доля и даёт нужное независимое множество.
Связывает деревья, двудольность и независимые множества.