Страница 68 номер 93, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
В некотором графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
Предположим, что в графе нет ни одного цикла. Граф не обязан быть связным, поэтому возьмём любую его компоненту: она связна и без циклов, то есть дерево. При \(k\) вершинах в ней \(k-1\) ребро, и сумма степеней равна \(2(k-1) = 2k - 2\).
Но все степени равны 3, а вершин \(k\), поэтому та же сумма равна \(3k\), и числа различны: \(3k - (2k - 2) = k + 2\), а \(k + 2\) больше нуля при любом \(k\). Противоречие показывает, что предположение неверно.
Ответ: цикл в таком графе есть обязательно: иначе каждая его часть была бы деревом, где сумма степеней равна \(2k - 2\), а при всех степенях 3 та же сумма равна \(3k\), и эти числа различаются на \(k + 2\).
В некотором графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
Предположим противное: пусть в графе нет ни одного цикла.
Граф не обязан быть связным, поэтому возьмём любую его компоненту связности. Она связна и циклов не содержит, то есть является деревом. Пусть в ней \(k\) вершин; тогда рёбер в ней \(k-1\), и сумма степеней её вершин равна \(2(k-1) = 2k - 2\).
С другой стороны, все степени равны 3, а вершин \(k\), поэтому та же сумма равна \(3k\). Но эти числа различны: \(3k - (2k - 2) = k + 2\), а \(k + 2\) больше нуля при любом числе вершин. Одна и та же сумма степеней не может равняться двум разным числам.
Полученное противоречие показывает, что предположение неверно.
Ответ: цикл в таком графе есть обязательно: иначе каждая его часть была бы деревом, где сумма степеней равна \(2k - 2\), а при всех степенях 3 та же сумма равна \(3k\), и эти числа различаются на \(k + 2\).
