Деревья и остовные деревья

1. В полном графе на четырех вершинах есть только 2 вида остовных деревьев: 1) цепь длины 4; 2) три вершины, "висящие"на четвертой.

Каждое дерево первого вида даст в остовный многочлен одночлен , , причем каждый одночлен будет представлен 2 раза.

Каждое дерево второго вида даст в остовный многочлен одночлен , где — "вершина"остова.

В итоге получим многочлен:

2. Распишем . Поскольку многочлен линеен по каждой переменной, получаем, что каждая из переменных живет только в одной из скобок. Тогда переменные вынуждены разбиться на скобки 2-2-1 или 3-1-1, что дает нам не более четырех мономчиков, противоречие.

3. Давайте сначала заметим, что можно последовательно выкидывать вершины по одной с сохранением связности, если связно. (Если несвязно, то просто 0 получится и все).

Для этого нужно подвесить за и поочередно удалять вершины с самого нижнего уровня. Теперь нужно понять, что при удалении только одной вершины граф остается хорошим. Для этого подставим 0 в . Получим, что все слагаемые, в которые входило в хотя бы первой степени, обнулились, а значит остались в точности те, где — висячая вершина. А все такие деревья устроены так: выбрано дерево в графе , и потом одна из вершин из окрестности соединена с . Тогда многочлен после подстановки нуля равен . Подстановка нуля сохраняет раскладываемость на множители, значит тоже раскладываемый, значит, при удалении вершины граф останется хорошим.

4. Сначала докажем вспомогательный факт про такой тип графов.

Лемма о раздвоении без добавления ребра. Пусть дан граф на вершинах. Рассмотрим граф , полученный из добавлением вершины и соединением ее со всеми вершинами из , но не самой . Тогда

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

Теперь давайте поймём, как устроены деревья в . Там мы тоже берём лес, который содержит все вершины, кроме , , и такой, что каждая его компонента содержит хотя бы одну вершину из , после чего одна из долей соединяется с обеими вершинами из и , а каждая из остальных долей — с ровно одной из этих вершин. Тогда в тех же обозначениях получается, что

Теперь очевидно, что второй сомножитель равен , и лемма доказана. ________________________

Пусть - граф из леммы 1. Мы в лемме 1 уже выяснили как устроены деревья в графе , поэтому нужно разобраться с тем, как они устроены в . Заметим, что они устроены так: мы снова берем лес с такими же условиями, а дальше делаем одно из двух - либо не проводим ребро между и , и это слагаемое такое же как в , либо проводим, и тогда каждую из долей соединяем с ровно одной из этих вершин. Стало быть, сумма всех первых слагаемых даст нам , а сумма вторых равна

Тогда получается, что

доказали требуемое.