Question

В графе с n вершинами степень каждой вершины не превосходит пяти. Докажите, что вершины можно раскрасить в три цвета так, что ребер с одноцветными концами будет не более n/2.

Answer 1

Ответ:

N=101, и k=3 и n=99, k=100

(но это не точно)

Пошаговое объяснение:

если помог можно лайк

Answer 2

Ответ:

Рассмотрим граф G с вершинами в городах, ребра которого соответствуют дорогам. Докажем, что вершины этого графа можно покрасить в  2N + 2  цвета правильным образом (то есть так, чтобы никакие две вершины одинакового цвета не были соединены ребром). Это равносильно утверждению задачи.

 Выберем по одному ребру в каждом нечётном цикле графа G. Назовём эти ребра плохими, а остальные – хорошими. Удалив из графа G плохие рёбра, мы получим граф, в котором нет циклов нечётной длины.

 Лемма. Вершины графа без нечётных циклов можно раскрасить правильным образом в два цвета.

 Доказательство. Достаточно доказать лемму для связного графа. Выберем вершину A и припишем каждой вершине число, равное минимальной длине пути до неё из A. Тогда два одинаковых числа не стоят рядом (иначе есть нечётный цикл). Раскрасив все чётные вершины в один цвет, а нечётные – в другой, получим требуемое.

 Таким образом, вершины графа G можно покрасить в два цвета (пусть это цвета a и b) так, что никакие две вершины одного цвета не соединены хорошим ребром.

 Поскольку через каждую вершину графа G проходит не более N нечётных циклов, то из каждой вершины выходит не более N плохих рёбер.

 Следовательно, мы можем раскрасить вершины графа G в  N + 1  цвет так, чтобы никакие две из них не были соединены в графе G плохим ребром. (Будем красить вершины по очереди. Добавляя очередную вершину A, заметим, что среди покрашенных ранее она соединена плохими ребрами не более, чем с N вершинами, следовательно, мы можем покрасить вершину A в цвет, отличный от цветов ранее покрашенных вершин, соединенных с A плохими рёбрами.)

 После этого у всех вершин изменим оттенок на светлый, если в первой раскраске она была покрашена в цвет a, и на тёмный, если она была покрашена в цвет b.

 В полученной раскраске используется  2N + 2  цвета (с учетом оттенков), и никакие две вершины одного цвета не соединены ребром

Answer 3

Давайте рассмотрим данное утверждение и докажем его по индукции.

Базовый случай: n = 1. В данном случае у нас есть только одна вершина, и она не имеет рёбер. Мы можем выбрать любой цвет для этой вершины, и условие по числу рёбер будет выполнено (0 ≤ 1/2).

Предположение индукции: Пусть утверждение верно для графа с n вершинами.

Шаг индукции: Докажем, что оно верно для графа с n+1 вершиной.

Пусть у нас есть граф G с n+1 вершиной. Рассмотрим вершину v, у которой степень меньше 5 (по условию задачи такая вершина обязательно существует). Удалим вершину v из графа G, вместе со всеми инцидентными ей рёбрами. Получим подграф G' с n вершинами.

По предположению индукции, подграф G' можно правильно раскрасить в три цвета так, чтобы рёбер с одноцветными концами было не более n/2. Добавим теперь вершину v обратно в граф.

Так как степень вершины v не превосходит 4 (по условию задачи), она имеет не более 4 инцидентных ей рёбер. Однако в подграфе G' уже есть как минимум n/2 рёбер с одноцветными концами (по предположению индукции).

Таким образом, у нас есть не более 4 рёбер, которые могут быть добавлены к вершине v, чтобы получить рёбра с одноцветными концами. Мы можем выбрать цвет для вершины v так, чтобы она соединялась с рёбрами разных цветов. Теперь у нас будет не более (n/2 + 4) = (n+8)/2 рёбер с одноцветными концами в графе G, который имеет n+1 вершину.

(n+8)/2 ≤ (n+1)/2, так как 8/2 = 4, а 4 ≤ 1 для любого n. Следовательно, мы доказали, что граф с n+1 вершиной также можно раскрасить в три цвета так, чтобы рёбер с одноцветными концами было не более (n+1)/2.

Из этого следует, что утверждение верно для любого графа с n вершинами.

Таким образом, мы доказали утверждение по индукции: вершины графа с n вершинами можно раскрасить в три цвета так, что рёбер с одноцветными концами будет не более n/2.