Изменения
Нет описания правки
'''1. ''' Для проверки первого свойства воспользуемся некоторыми особенностями плоских графов. Из [[Формула_Эйлера | формулы Эйлера]] для плоских графов, в частном случае триангуляции, ограниченной тремя ребрами, следует, что число вершин $N$ и число ребер $e$ связаны соотношением
$e = 3N - 6$.
Пока в триангнуляции есть внутренние вершины (в противном случае задача тривиальна), степень каждой из трех граничных вершин не меньше трех. Поскольку существует $3N - 6$ ребер, а каждое ребро инцидентно двум вершинам, то сумма степеней всех вершин меньше $6N$. Отсюда сразу следует, что не менее $ \frac{N}{2}$ вершин имеет степень меньше 12. Следовательно, пусть $K = 12$. Пусть также $v$ {{---}} число выбранных вершин. Поскольку каждой из них инцидентно не более $K-1 = 11$ ребер, а три граничные вершины не выбираются, то мы имеем
$v \ge \left \lfloor \frac{1}{12}(\frac{N}{2} - 3) \right \rfloor $.
Следовательно, $a \cong 1 - \frac{1}{24} < 0,959 < 1$, что доказывает справедливость свойства 1.
