Связность и связные подграфы (клики)

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

Теперь покажем, что меньшего числа дорог может не хватить. Рассмотрим граф из ориентированный треугольников. Тогда ребра можно проводить только между вершинами из разных треугольников. Задача министерства такова. Есть граф на треугольниках, нужно провести ребра, чтобы граф стал сильно связным. Для того чтобы граф стал просто связным, нужно хотя бы ребер, но тогда граф станет лишь деревом, поэтому министерству необходимо хотя бы дорог.