Чтобы определить минимальное количество рёбер, необходимых для создания связного графа, можно воспользоваться следующим подходом: 2

1. Найти количество входящих и исходящих степеней каждой вершины графа с помощью DFS. 2
2. Если входная или исходная степень вершины больше 1, то считать её только 1 и подсчитать общую входную и исходную степень графа. 2
3. Минимальное количество рёбер, необходимых для создания сильно связного графика, равно max (N — общая степень входа, N — общая степень выхода). 2

Также можно использовать теорему о количестве рёбер в дереве: 34 если граф из n вершин является деревом, в нём ровно n − 1 ребро. 34

Ещё один подход заключается в том, что минимальное количество рёбер в связном графе достигается тогда, когда этот граф — дерево. 3