О графах с цветными ребрами (ответы и решения)

1. Пусть красное ребро означает, что два делегата могут объясниться на одном языке, а синее - что не могут. Если красного треугольника нет, то по свойству 2 должен быть треугольник с синими сторонами. Но это противоречит условию.

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

Предположим, что нет красного треугольника. Пусть какая-нибудь вершина A соединена красными ребрами с B₁, B₂, B₃ и B₄, синими - с C₁, C₂, C₃ и C₄. Ребра вида B_iB_j - синие (рис. 1). Каждая из B_i соединена тремя красными ребрами с вершинами C_j, Два красных ребра связывают вершины вида C между собой (поскольку красных ребер B_iC_j - двенадцать). Пусть B_i связана красными ребрами с C₁ C₂, и C₃. Между собой C₁ C₂, и C₃ соединены синими ребрами, иначе образовался бы треугольник с красными сторонами (рис. 2).

Тогда C₄ принадлежит двум красным ребрам вида. C₄C_i, например, C₄C₃ и C₄C₂. Но C₄ принадлежит еще двум красным ребрам. Одно из них, - например, C₄B₂ (рис. 3). Хотя бы одно из ребер B₂C₂ и B₂C₃ - тоже красное, то есть хотя бы один из треугольников B₂C₃C₄ и B₂C₂C₄ имеет красные стороны.

3. Имеем полный граф с n вершинами и ребрами двух цветов (синее ребро - двое могут объясниться на каком-нибудь языке, красное - не могут). По условию, среди любых четырех вершин графа всегда найдется, по меньшей мере, одна, синяя степень которой равна трем.

Случай, когда все ребра синие, тривиален. Пусть найдется красное ребро AB. Добавим еще какие-нибудь две вершины C и D. Из четырех вершин A, B, C и и найдется хотя бы одна, синяя степень которой равна трем. Это - C или D. Пусть, например, синюю степень три имеет C. Добавим еще одну вершину - E. Из вершин A, B, C, E или C или E имеет синюю степень, равную трем. В обоих случаях C соединена синим ребром с E. Так переберем все вершины. В итоге окажется, что C соединена синими ребрами со всеми вершинами графа. Во всякой четверке вершин, включающей A и B, есть вершина, соединенная синими ребрами со всеми остальными вершинами графа. Отсюда, кроме A и B существует, самое большее, одна вершина, не соединенная синими ребрами со всеми остальными.

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

Рассмотрим некоторое красное ребро АВ. Пусть синяя степень вершины A равна k.

Предположим, что k >= n/2. Легко видеть, что B соединена красными ребрами с теми вершинами, с которыми A соединена синими ребрами. Поэтому, если красная степень вершины B равна l, то l = k + 1 > k >= n/2.

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

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