Доказать утверждение о графах

[frankenstein]

Не знаю как подобраться к этой задаче.
Как доказать что вне зависимости от координат вершин графа, вершины
можно соединить ребрами (не обязательно прямыми), так что бы ни
какие два ребра не пересекались?

[mihailm]

Ну и утверждение!
А от координат точек ребер зависит?

[svv]

Доказательство. Соединяем на плоскости $1$-ю вершину со $2$-й, $2$-ю с $3$-й и так далее до $n$-й.
Опровержение. Непланарный граф невозможно уложить на плоскость без пересечения ребер.

[frankenstein]

Да, я что-то не очень ясно сформулировал задачу.
Допустим у нас есть плоский граф, и он как-то размещен
на плоскости.
Допустим мы на время удалили все ребра, а вершины
перемешали.
После чего заново расставили его ребра, так, что
никакие два из них не пересекаются.
Надо доказать что это всегда возможно, вне зависимости
от положения вершин на плоскости.

[nikvic]

frankenstein в сообщении #847563 писал(а):

Допустим у нас есть плоский граф, и он как-то размещен
на плоскости.

Планарный

[frankenstein]

nikvic в сообщении #847564 писал(а):

frankenstein в сообщении #847563 писал(а):

Допустим у нас есть плоский граф, и он как-то размещен
на плоскости.

Планарный

Ну, да

[patzer2097]

frankenstein в сообщении #847563 писал(а):

Надо доказать что это всегда возможно, вне зависимости от положения вершин на плоскости.

докажите, что на достаточно малое расстояние вершину можно перенести всегда (сохраняя структуру плоского графа)
потом рассмотрите какую-нибудь кривую, которая имеет концы в начальном положении вершины и в конечном (эту кривую можно выбрать кусочно-линейной). наконец, воспользуйтесь компактностью этой кривой