Правильный n-угольник разбит диагоналями на треугольники (диагонали пересекаются разве что в вершинах многоугольника). Вершинами графа T∗ являются треугольники разбиения. Два треугольника связаны ребром в графе T∗, если у них есть общая сторона. Докажите, что T∗ — дерево.

Решение. Нам известно, что граф на N вершинах является деревом, если и только если он связен и
количество ребер в нем равно N − 1. Докажем поочередно эти два факта для графа T∗.
Cвязность: Необходимо показать, что от любого треугольника разбиения до любого другого можно
"добраться через другие треугольники". Рассмотрим любые две точки внутри n-угольника (не лежащих на
диагоналях разбиения) и проведем соединяющий их отрезок. Он пересечет какое-то количество диагоналей
(воpможно, 0) и, тем самым, какое-то количество треугольников разбиения. Это индуцирует путь в графе T∗:
в точности по вершинам, соответствующим этим треугольникам (причем в той же последовательности).

Количество ребер: Докажем, что каково бы ни было разбиение выпуклого n-угольника на треугольники непересекающимися диагоналями, в нем обязано быть n − 2 треугольника и n − 3 диагонали. Тогда число вершин в T∗ равно n − 2, а число ребер равно n − 3, что и требовалось. Будем вести индукцию по n.
База индукции: n = 3. Очевидно, имеем 1 треугольник и 0 диагоналей.
Переход: пусть для всех 3 ≤ m < n утверждение для m-угольника доказано. Докажем его для nугольника. Итак, пусть выпуклый n-угольник разбит на треугольники непересекающимися диагоналями.
Рассмотрим любую из них (см. рис. ниже). Она разбивает n-угольник на два выпуклых многоугольника:
k-угольник S1 и (n − k + 2)-угольник S2 (отметим, что S1 и S2 имеют ровно две общие вершины, поэтому
суммарно в них n + 2 вершины). Мы можем применить предположение индукции к многоугольникам S1 и
S2, поскольку остальные диагонали формируют разбиения этих многоугольников на треугольники.
Тем самым, для разбиения S1 имеем k − 2 треугольника и k − 3 диагонали, а для разбиения S2 имеем
(n − k + 2) − 2 = n − k треугольников и (n − k + 2) − 3 = n − k − 1 диагоналей.
Значит, в разбиении исходного n-угольника было (k − 2) + (n − k) = n − 2 треугольника. А количество
диагоналей равнялось (с учетом первой диагонали): (k−3)+ (n−k−1)+ 1 = n−3. Именно это и требовалось
показать!