Остовное дерево с максимальным количеством листьев: различия между версиями

Общая структура аргумента вычисляется при помощи минимального контрпримера согласно приоритетам, заданным в результате выбора (3), который обычно ссылается на выбор (2). Доказательство развивается посредством серии небольших шагов, состоящих из серии утверждений по поводу структуры, которые в сумме ведут к получению детального представления структур на «границе» и, следовательно, позволяют определить границу размера G, на основе которой выводится заключение леммы. Полное доказательство объединяет серию утверждений по поводу пограничного дерева, различных множеств вершин и индуктивных приоритетов индукции и формирует основное неравенство, на основе которого производится доказательство по индукции, и ядро задачи размера 3,5k.