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

Тогда В Г Р 2.

Тогда В Г Р 2.

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

Если 1(А) = к для какой-то вершины А, то все доказано. А если нет, и для всех вершин 1(Х) ^ к — 1, то мы можем раскрасить вер­шины по-новому, поставив в соответствие каждой вершине цвет с номером 1(X). А это противоречит тому, что исходный граф является к-дольным.

Заметим, что мы доказали даже более сильное утверждение: что найдется путь, в котором цвета вершин идут в произвольном наперед заданном порядке.

Определение 6. Граф называется планарным, если его можно на­рисовать на плоскости, изобразив вершины точками, а ребра (или дуги) — непересекающимися кривыми. Граф, который нарисован на плоскости указанным выше образом, называется плоским. Части, на которые плоский граф делит плоскость (включая внешнюю часть) называются его гранями.

Задача 28. Какие графы из задач 1, 2 и 3а первого листка про графы являются планарными?

Решение. Планарными являются все графы из задач 1, 2 и 3. Заметим, что планарность графа из задачи 3а доказывать не нужно — он уже нарисован на плоскости (карте мира).

Задача 29 (формула Эйлера). Пусть в неориентированном плоском связном графе В вершин, Р ребер и Г граней. Тогда В + Г — Р = 2.

Решение. Предположим, что Г > 1. Тогда возьмем произвольные две соседние грани и сотрем произвольное ребро между ними. Число ре­бер уменьшится на 1, и число граней уменьшится на 1, следовательно, сумма В+Г — Р не изменится.

Таким образом, мы спустимся к случаю, когда Г = 1. Заметим тогда, что в полученном графе не может быть циклов (иначе было бы хотя бы две разные грани), значит, он является деревом, и В=Р +1. Следовательно, В + Г — Р = (Р +1) +1 — Р = 2, что и требовалось дока­зать.