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

Теперь можно применить предположение индукции.

Теперь можно применить предположение индукции.

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

Задача 2. Докажите, что граф с п вершинами, степень каждой из

п — 1

которых не менее ——, связен.

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

не больше ^ — 1, что меньше —противоречие.

Задача 3. В связном графе все вершины имеют степень 100. Докажи­те, что после удаления любого из ребер он остается связным.

Указание. Воспользуйтесь тем, что в любой связной компоненте графа сумма степеней вершин четна, так как она равна удвоенному числу ребер в этой компоненте.

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

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

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

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