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

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

Подсказка

Построим новый граф, вершинами которого будут остовные деревья нашего графа.

Решение

Пусть $G$ — наш граф, обозначим через $2 k$ количество его вершин. Построим новый граф $H$ , вершинами которого будут остовные деревья графа $G$ . Вершины, соответствующие деревьям $T_{1}$ и $T_{2}$ соединим ребром тогда и только тогда, когда в деревьях $T_{1}$ и $T_{2}$ совпадают $2 k-2$ ребра (то есть одно дерево получается из другого заменой одного ребра). Рассмотрим любое остовное дерево $T$ графа $G$ и рассмотрим любое его ребро $e$ . Уберем ребро $e$ , вершины дерева $T$ распадутся на две компоненты связности $V$ и $U$ . Так как степень каждой вершины графа $G$ четна, то в графе $G$ четное число ребер с одним концом в $V$ и другим концом в $V$ . Заменив ребро $e$ на любое другое ребро между $V$ и $U$ , мы получим все остовные деревья, получающиеся из $T$ заменой ребра $e$ на какое-то другое ребро. Количество таких деревьев нечетно. То же самое верно для любого ребра дерева $T$ . Так как в $T$ нечетное число ребер, то из соответствующей дереву $T$ вершины графа $H$ выходит нечетное число ребер. Это означает, что количество вершин графа $H$ (то есть, остовных деревьев графа $G$ ) четно.