Алкосики 9

Задача 3

Допустим, что мы убали воздушный транспорт. Пусть осталась какая-то вершина, которая улетела в другую компоненту связности - это значит, что она была соединена со всеми остальными n-1 вершинами воздушным транспортом. Теперь попробуем из того же графа убрать водный транспорт. Второй аналогичной вершины уже не может существовать, потому что она соединена воздушным транспортом с прошлой вершиной. То есть, если убирание одного из типов транспорта нарушает связность графа, то мы можем убрать другой и получить вершину, связанную со всеми остальными, что автоматически значит, что из каждой вершины можно добраться в каждую

Задача 2

Пусть мы каким-то образом соединили некоторое количество ребер одним из цветов так, чтобы условие не выполнялось. Значит есть хотя бы (C_6^3)=20 недорисованных (без одного ребра) треугольников каждое ребро используется по 4 раза, так что есть минимум 5 ребер, которые мы пока что не провели. Раз мы не провели 5 ребер, то провели 10, что значит, что каждая вершина соединена как минимум с одной. То есть, мы не можем провести оставшиеся пять ребер другим цветом так, чтобы не создать цикла из трех точек (до этого могли из одной точки во все остальные). ЧТД

Задача 4

Пронумеруем как-нибудь вершины в графе, далее будем красить их по возрастанию номера - каждая вершина получает минимальный цвет, которого нет у ее соседей. Т.к. из каждой вершины выходит не более k ребер, а цветов всего k+1, такой цвет обязательно найдется