Король и дороги

[FedorTokarev]

Во владении короля имеется $100$ городов, которые не соединены дорогами. Король захотел построить дороги между некоторыми парами городов так, что если два города не связаны новой дорогой, то из одного города в другой можно добраться по крайней мере двумя разными маршрутами по новым дорогам, дополнительно проезжая ровно через один город. Какое наименьшее количество дорог может быть построено?

Вот такая задача! Пожалуйста, подскажите, направьте на путь решения :)

[StaticZero]

Пусть города $\mathrm A$ и $\mathrm B$ не соединены дорогами, а каждый из них соединён со всеми остальными городами. Можно ли убрать хотя бы одну любую дорогу, чтобы не нарушить условие задачи?

[Skeptic]

Сначала решите такую задачу.
Соединяете дорогами все города последовательно. Сколько новых дорог надо проложить для связности городов, если убрать одну дорогу?
Затем распространиете решение на параллельные пути.

[provincialka]

Раз все города попарно связаны, то граф связный. Если не каждый город связан с каждым, то в нем есть циклы.

Вообще-то задачка по типу олимпиадная. Это не с текущей олимпиады какой-нибудь?

[Skeptic]

Граф должен быть связан.
На циклы нет ограничений. Требуется только существование не менее двух путей между любыми городами.

[provincialka]

Что значит "на циклы нет ограничений"? Если есть два разных пути из $A$ в $B$, они и образуют цикл.
Теперь из каждого пункта можно сделать выводы: какое наименьшее число ребер может быть у графа?

Собственно, мы кому подсказываем? Где ТС?