Всё просто - для выпуколого решение единственно, для невыпуклого (даже без самопересечений) - решение не единственно.

Например, условие "для каждой вершины соседние вершины одновременно являются ближайшими вершинами" так же будет достаточным.

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

для обоих условий ("выпуклость" и "для каждой вершины соседние вершины одновременно являются ближайшими вершинами") решение единственно с точностью до направления обхода и выбора начальной вершины.

Для выпуклого - да, а для критерия

для каждой вершины соседние вершины одновременно являются ближайшими вершинами

нет. Возьмите окружность, одну точку бросьте в центр, остальные разбросайте по окружности так, чтобы расстояние между точками, лежащими на окружности было меньше радиуса окружности (уже 4х точек на окружности должно хватить). Так какие именно две точки на окружности в соответствии с Вашим критерием Вы соедините с той что в центре?

Во-первых, тогда нужно не меньше 6 точек на окружности. Или я не правильно понял вашу идею?

Да, нужно минимум 7 точек.

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

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

В-третьих, наверное, будет более правильно это условие сузить до "для каждой вершины соседние вершины одновременно являются ближайшими вершинами и нет других верших находящихся на расстоянии, равном расстоянию до соседних вершин"

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

Вообще-то с точки зрения данного раздела всё это обсуждение не очень уместно, тут было бы правильнее просто запостить сишный код реализующий тупой перебор трудоёмкостью O(N^4).