математическая-логика - Количество остовных деревьев в графе с n вершинами и n ребрами.

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

Если же граф связен, то одно остовное поддерево имеется. В нём n-1 ребро. Ещё одно ребро к нему добавляется. Пусть концы этого ребра соединены в остовном поддереве простым путём длины k. Тогда получается цикл длины k+1. Из него можно удалить любое ребро, получая остовное поддерево. Другие рёбра, не входящие в этот цикл, удалять нельзя -- дерева при этом не будет, а будет несвязный граф.

Поэтому ответом будет число k+1 -- длина простого цикла в данном графе. Такой цикл в условиях задания ровно один. Но значение k может принимать любые значения от 1 до n.