Принцип крайнего

Первый способ. Рассмотрим всевозможные разбиения точек на пары и соединим их отрезками. Выберем разбиение на пары, в котором сумма длин проведенных отрезков минимальна. Такое разбиение существует, так как количество способов разбить на пары конечно.

Предположим, что какие-то два из отрезков ( и ) имеют общую точку .

Применим неравенство треугольника:

Сложим эти неравенства:

Тогда если мы поменяем пары в разбиении на пары то сумма длин проведенных отрезков уменьшится. Но это противоречит минимальности суммы длин во взятом разбиении на пары.

Второй способ. Мысленно проведем всевозможные отрезки между точками. Их конечное число, а возможных направлений прямых на плоскости бесконечно. Тогда найдется прямая, которая не параллельна ни одному из отрезков. Введем декартову систему координат на плоскости, где эта прямая будет осью абсцисс.

Так как ось абсцисс не параллельна ни одному из отрезков между точками, у всех точек будут различные ординаты. Тогда пронумеруем точки сверху вниз. И проведём отрезки, соединяющие самые “верхние” точки, затем следующие по высоте точки и так далее. (Пример на картинке)