Раскраска графов

Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина , и она соединена ребрами цвета 1 с вершинами . Поскольку , то остались еще вершины , каждая из которых соединена с вершиной ребром какого-то другого цвета.

Решение 1. Предположим противное, пусть в любом треугольнике есть два одноцветных ребра. Рассмотрим вершину, из которой выходит наибольшее количество ребер одного цвета (или любую из них, если таких несколько). Пусть это вершина , и она соединена ребрами цвета 1 с вершинами . Поскольку , то остались еще вершины , каждая из которых соединена с вершиной ребром какого-то другого цвета. Рассмотрим вершину , пусть она соединена с ребром цвета . Тогда должна быть соединена с каждой из вершин либо ребром цвета 1 , либо ребром цвета (иначе будет треугольник с разноцветными сторонами). Если все эти ребер окрашены в цвет , то всего из вершины выходит ребро цвета , что противоречит выбору вершины и цвета 1 . Следовательно, хотя бы одно из этих ребер окрашено в цвет 1. Таким образом, из каждой вершины выходит хотя бы одно ребро цвета 1 , и всего мы имеем ребро цвета 1 , что противоречит условию. Следовательно, обязательно найдутся три вершины, все три ребра между которыми покрашены в разные цвета.

Решение 2. Пусть в любом треугольнике есть два одноцветных ребра. Так как ребер любого цвета не более , то они образуют несвязный граф на данных нам вершинах. Для каждого цвета такой граф распадается хотя бы на две компоненты связности. Среди всех таких компонент связности (для всех цветов) найдем наибольшую по количеству вершин компоненты связности (пусть ее ребра окрашены в цвет 1). Очевидно, существует вершина , не вошедшая в . Рассмотрим любую вершину из , она соединена с ребром не цвета 1 , пусть это ребро цвета 2 . Если вершина из соединена с ребром цвета 1 , то также соединена с ребром цвета 2 (иначе будет треугольник будет иметь разноцветными ребрами). Такими же рассуждениями мы получим, что соединена со всеми вершинами компоненты связности ребрами цвета 2 , но тогда существует компонента связности цвета 2 , содержащая все вершины из и вершину . Противоречие с максимальностью компоненты связности .

Допустим, что каждый город соединен не более чем с двумя другими. Тогда все дороги объединяются в циклы (замкнутые маршруты) и цепи (незамкнутые маршруты), не связанные между собой.

Допустим, что каждый город соединен не более чем с двумя другими. Тогда все дороги объединяются в циклы (замкнутые маршруты) и цепи (незамкнутые маршруты), не связанные между собой. В каждой цепи и каждом цикле четной длины отметим города красным и синим цветами так, чтобы цвета чередовались, а в каждом цикле нечетной длины отметим красным какие-либо два соседних города, а остальные снова покрасим так, чтобы их цвета чередовались. Тогда синие города вообще не будут связаны дорогами, а дорог, соединяющих красные, будет столько же, сколько циклов нечетной длины. Поскольку в каждом нечетном цикле не меньше трех дорог, дорог, соединяющих одноцветные города, будет не больше трети от общего числа дорог.

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

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

Ответ: Нет.

Решение. Понятно, что после каждой из указанных операций остается связный граф, а в конце должно получиться дерево. Вершины дерева можно раскрасить в два цвета так, чтобы у всех его ребер были концы разных цветов. Если мы будем по очереди добавлять убранные ребра (сначала — убранное последним, потом — предпоследним и т.д.), то это свойство не нарушится (т.к. 4 — четное число). Но вершины полного графа, который по условию был в начале, так раскрасить нельзя.