Изменения

|statement=<tex> S(P) </tex> является деревом, содержит <tex> n </tex> связных граней, не более <tex> n - 2 </tex> внутренние вершины и не более <tex> 2 n - 3 </tex> рёбер.

Каждая грань <tex> f(e) </tex> начинается образовываться во время стягивания ребра <tex> e </tex>, и даже если на ребре произошёл <tex> split\ event </tex>, сама грань не могла разделиться. Построение грани <tex> f(e) </tex> завершается, когда ребро <tex> e </tex> полностью стягивается. А новые рёбра появляться И это ребро дальше не могутможет появиться снова, поэтому граней в <tex> S(P) </tex> столько, сколько сторон в многоугольнике, то есть ровно <tex> n </tex>. То, что <tex> S(P) </tex> является деревом, а каждая грань легко доказывается по индукции. База верна, когда внутренняя вершина всего одна. Тогда у <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> листьями будут вершины многоугольника. Такой граф очевидным образом будет связнаядеревом. Если в <tex> \mathrm{straight}\ \mathrm{skeleton}\ k </tex> внутренних вершин, то рассмотрим самый первый <tex> edge\ event</tex>. Поэтому граней Он закончился в какой-то внутренней вершине <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, у неё есть смежные листья {{---}} вершины, инцидентные этому ребру, {{---}} и из неё достижимы другие <tex> \mathrm{straight}\ \mathrm{skeleton}' </tex>ы, с не более чем <tex> k - 1 </tex> внутренними вершинами, и они являются деревьями по предположению индукцию. Тогда получаем, что <tex> S(P) </tex> столькодля <tex> k </tex> вершин тоже будет деревом. Внутренние вершины в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> имеют [[Основные определения теории графов#def_graph_degree_1 | степень]] не меньше <tex> 3 </tex> {{---}} простой перебор всех случаев <tex> event'</tex>ов (степень будет больше, сколько сторон если в многоугольникеодной вершине совпало несколько событий). Так как <tex> S(P) </tex> имеет <tex>n</tex> листьев, то внутренних вершин будет не больше <tex> n - 2 </tex>, а рёбер так как <tex> 2n - 3 S(P) </tex>является деревом, что следует из того, что то рёбер у него будет не более <tex> S(P) 2 n - 3 </tex> является деревом.