Я решал так : 

1)Выписываю расстояния между всеми точками в  массив (d[].dist) при этом запоминая сами точки(d[].p1 , d[].p2)

.2)Сортирую эти расстояния по убыванию.

3)До тех пор пока могу удалять , удаляю (т.е. пока из вершины d[].p1 (d[].p2) есть хотя бы 2 ребра).

4)Вывожу ребро на котором я остановился (не смог удалить).

Мое доказательство :

1)В конце останется какая-та вершина с одним ребром(условие останова).

2)Оставшиеся ребра меньше моего (все остальные удалены) .

3)У данной вершины все удаленные ребра больше оставленного следовательно нам не выгодно менять ответ.

Однако мне так и не удалось пройти дальше седьмого теста , что я делал не так???