Где ошибка?

[ewert]

slavav в сообщении #1204818 писал(а):

Думаю, что любой планарный граф можно гомеоморфно перевести в прямолиненый.

Перевести-то можно. Только рёбра запросто могут начать пересекаться.

Возьмете, например, четыре точки и расположите их сначала в вершинах квадрата, а потом звездой.

[slavav]

Нужно общее доказательство, что есть процедура, которая сохраняет число рёбер и позволяет построить любую триангуляцию. То что вы сделали с рёбрами $AC$ и $BE$ называется edge flip. Верно утверждение что последовательностью edge flip можно перевести любую триангуляцию в любую другую. Но доказательство это весьма сложно (и интересно). Гораздо проще вывернуть индукцию.

[AV_77]

Someone в сообщении #1204814 писал(а):

А "отрезки" обязательно прямолинейные? Что-то не соображу, существенно это или нет.

Существенно. В конструкции

$$ \xymatrix{a \ar@{-}[dd]_1 \ar@{-}[rr]_2 \ar@{-}[dr]_1 & & \circ \ar@{-}[ld]_2 \ar@{-}[dd]_1 \\ & \circ & \\ \circ \ar@{-}[ru]_2 \ar@{-}[rr]_1 & & b \ar@{-}[lu]_2 } $$

можно добавить криволинейное ребро, соединяющее вершины $a$ и $b$.

[slavav]

Ребро $(a, b)$ лежит вне выпуклой оболочки.

-- 30.03.2017, 21:42 --

Формула для числа рёбер - следствие формулы Эйлера для триангуляции сферы, где разрешена одна нетреугольная грань - внешность выпуклой оболочки. Формула Эйлера доказывается методами топологии. Так что прямолинейность роли не играет.

[Someone]

AV_77 в сообщении #1205029 писал(а):

Существенно.

Понял. Но тогда количество отрезков, которое можно провести, зависит от расположения точек. И мне не очевидно, что оно не зависит от того, какие именно отрезки проведены. Хотя пример я придумать не смог.

[slavav]

Вы не сможете привести пример. На количество отрезков, которые можно провести влияет только общее число точек и число точек на границе выпуклой оболочки. Выше в этой теме это утверждение доказано двумя способами, ещё два способа упоминались вскользь.

[AV_77]

slavav в сообщении #1205058 писал(а):

Ребро $(a, b)$ лежит вне выпуклой оболочки.

Ну и что? Его же можно провести.

[slavav]

Моё замечание касалось того факта что когда вы проводите ребро вне выпуклой оболочки, вы меняете $K$ в формуле для числа рёбер.