Задача 044 — Задачи на Графы

Докажите, что у двудольного графа с четным числом вершин и четным числом ребер количество остовных деревьев четно. (Остовное дерево — это подграф исходного графа, содержащий все его вершины и являющийся деревом.)

Подсказка

Всего из дерева получается нечётное число графов, в которых добавлено ещё одно ребро.

Решение

Пусть $G$ — наш граф, $\mathrm{T}(G)$ — множество всех остовных деревьев графа $G$ , а М( $G$ ) — множество всех остовных подграфов графа $G$ , имеющих ровно один цикл. Рассмотрим произвольное дерево $T \subset \mathrm{~T}(G)$ . В нем нечетное число ребер, следовательно, количество не вошедших в $T$ ребер графа $G$ также нечетно. Если к дереву $T \subset \mathrm{~T}(G)$ добавить любое не вошедшее в него ребро графа $G$ , то получится граф из $\mathrm{M}(G)$ . Всего таким образом из дерева $T$ получается нечетное число графов из $\mathrm{M}(G)$ . Наоборот, рассмотрим любой граф $H \subset \mathrm{M}(G)$ и его единственный цикл $Z$ . Граф $H$ может быть получен добавлением ребра к тем деревьям, которые получаются из $H$ удалением одного из ребер цикла $Z$ . Так как граф $G$ двудольный, то в цикле $Z$ — четное число ребер, следовательно, у графа $H$ — четное число остовных деревьев-«»предков»». Отсюда следует, что в множестве $\mathrm{T}(G)$ четное число остовных деревьев.