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

В дереве T 80 вершин. Набор из 39 независимых ребер (не имеющих общих вершин) будем называть толстым паросочетанием. Известно, что дерево $T$ имеет 820 различных толстых паросочетаний. Докажите, что $T$ — путь.

Подсказка

Будем доказывать индукцией по $n$ , что дерево на $2 n$ вершинах имеет не более $C_{n+1}^{2}$ (толстых) паросочетаний с $n-1$ независимыми рёбрами. Как выглядит дерево, если $n \geqslant 3$ и толстых паросочетаний ровно $C_{n+1}^{2}$ ? А при $n=2$ ?

Решение

Решение. Будем доказывать индукцией по $n$ , что дерево на $2 n$ вершинах имеет не более $C_{n+1}^{2}$ (толстых) паросочетаний с $n-1$ независимыми рёбрами. Причём если $n \geqslant 3$ и толстых паросочетаний ровно $C_{n+1}^{2}$ , то дерево является путем. А при $n=2$ граф является или путем, или «графом-ёжиком».

При $n=2$ существуют только такие деревья. Докажем переход. Пусть $T$ — дерево на $2 n$ вершинах, $n \geqslant 3$ . Так как дерево — это двудольный граф, его вершины можно разбить на две доли $V_{1}$ и $V_{2}$ . Заметим, что любое толстое паросочетание содержит по $n-1$ вершин из долей $V_{1}$ и $V_{2}$ . Следовательно, раз уж толстые паросочетния вообще существуют, возможны три случая, два из которых симметричны.
1. $\left|V_{1}\right|=n+1,\left|V_{2}\right|=n-1$ или $\left|V_{1}\right|=n-1,\left|V_{2}\right|=n+1$ . Разберём первый случай, второй доказывается аналогично. Заметим, что в любом толстом паросочетании не участвуют 2 вершины из доли $V_{1}$ . Количество способов выбрать две вершины из $V_{1}$ равно $C_{n+1}^{2}$ . Значит, толстых паросочетаний не более $C_{n+1}^{2}$ . Предположим, что их ровно $C_{n+1}^{2}$ . Тогда для любых двух вершин $u, v \in V_{1}$ существует толстое паросочетание, не содержащее вершины $u$ и $v$ . Но такого не может быть. Действительно, количество рёбер в дереве равно $2 n-1$ , а $\left|V_{2}\right|=n-1$ . Так как $n \geqslant 3$ , в доле $V_{2}$ есть вершина $x$ степени не более 2. Тогда без вершин из $V_{1}$ , среди которых есть все соседи $x$ , толстое паросочетания построить невозможно, противоречие.
2. $\left|V_{1}\right|=n,\left|V_{2}\right|=n$ . Подвесим граф за вершину. Пусть $v$ — висячая вершина последнего уровня, а $u$ — её сосед на предыдущем уровне. Без ограничения общности будем считать, что $v \in V_{1}$ . Если у вершины $u$ есть ещё одна соседняя висячая вершина $w$ , то любое толстое паросочетание не содержит одну из вершин $w$ или $v$ , и одну из вершин $V_{2}$ . Тогда толстых паросочетаний не больше $2 n<C_{n+1}^{2}$ при $n \geqslant 3$ .

Пусть у вершины $u$ нет соседних висячих вершин, кроме $v$ . Разобьём толстые паросочетания $T$ на два типа, первый тип — не содержащие $v$ , второй тип — содержащие ребро $u v$ . Паросочетаний первого типа не более $n$ , так как они не содержат $v$ и одну из вершин $V_{2}$ , коих $n$ . Все паросочетания второго типа образуют толстое паросочетание дерева $T^{\prime}=T-u-v$ , причём в $T^{\prime}$ поровну вершин в долях. По предположению индукции в дереве $T^{\prime}$ не более $C_{n}^{2}$ толстых паросочетаний. Значит, в $T$ не более $C_{n}^{2}+n=C_{n+1}^{2}$ толстых паросочетаний. Более того, если в дереве $T$ ровно $C_{n+1}^{2}$ толстых паросочетаний, то паросочетаний первого типа ровно $n$ , второго — ровно $C_{n}^{2}$ , а дерево $T^{\prime}$ — это путь $a_{1} a_{2} \ldots a_{2 n-2}$ . Если сосед $u$ — это $a_{1}$ или $a_{2 n-2}$ , то $T$ — путь. Иначе из соображения чётности одна из вершин $a_{2}$ и $a_{2 n-3}$ лежит в доле $V_{2}$ дерева $T$ (пусть $a_{2}$ ). Но тогда при удалении вершин $v$ и $a_{2}$ дерево не имеет паросочетания. Следовательно, паросочетаний первого типа меньше $n$ , противоречие. Индукционный переход доказан.