Таблицы Брадиса

Но а, поэтому У

Но а, поэтому У

Элементы математики в задачах - Г. А. Мерзон

Теперь предположим, что найдется такое X, что |а^)| = |X|. Обо­значим через X дополнение X в множестве вершин первой доли. Мы -Ф-                                                                                             утверждаем, что для множеств X и а{Х) и X и а(Х), рассматриваемых                                                                           ф

по отдельности, верны условия теоремы Холла.

Для X это является тавтологией, докажем для X. Пусть У с X, тогда |X и У| ^ |а^ и У)|. Тогда |X| + |У| = |X и У| ^ |а^ и У)| ^ |а^)| +

+ |а(У)|. Но |X| = |а(X)|, поэтому |У| ^ |а(У)|, что и требовалось.

Теперь можно применить предположение индукции. Все возможные случаи разобраны, теорема доказана.

Задача 26* (обобщение задачи 21). Докажите, что в любом регу­лярном двудольном неориентированном графе есть совершенное па- росочетание.

Решение. Решение задачи следует из теоремы Холла. Регулярность графа означает, что степени всех его вершин равны. Покажем, что |X| ^ |а^)| для любого множества X вершин из первой доли. Если |X| < |а^)| для какого-то множества |X| и степень каждой вершины равна к, то число ребер, выходящих из |а^)|, заведомо больше к|X|.

Так как |X| < |а(X)|, степень как минимум одной вершины из |а(X)| должна быть больше к, что неверно.

Теперь, поскольку VX |X| ^ |а^)|, утверждение задачи следует из теоремы Холла.

220                                    Теория графов 2

Задача 27*. Верно ли, что при любой правильной раскраске к-доль- ного неориентированного графа в к цветов найдется путь из к раз­ноцветных вершин?

Решение. Да, верно. Будем обозначать цвета, в которые раскрашены вершины, натуральными числами от 1 до к. Тогда любой вершине X можно поставить в соответствие число 1(X) —число путей, заканчи­вающихся в вершине X и таких, что номера цветов вершин строго возрастают вдоль пути.