Свойство 3. Если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с красными сторонами и синими диагоналями.
В формулировке свойства 3 можно заменить слово "красный" на "синий" и одновременно слово "синий" на "красный", то есть речь пойдет о пятиугольнике с синими сторонами и красными диагоналями. Это понятно, поскольку для пятиугольника и только для него характерно, что его диагонали образуют также пятиугольник.
Задача 3. В течение дня двое из шести телефонных абонентов могут поговорить друг с другом по телефону, а могут и не поговорить. Докажем, что всегда можно указать две тройки абонентов, в каждой из которых все переговорили друг с другом или все не переговорили.
Решение. Пусть у полного графа с шестью вершинами красные ребра соответствуют парам абонентов, которые говорили друг с другом по телефону, синие - тем, кто не говорил. Тогда в графе найдется хотя бы один треугольник, , с одноцветными сторонами.
Остается показать, что обязательно найдется еще и второй такой треугольник.
Временно исключим из рассмотрения одну из его вершин, скажем , вместе с ребрами, принадлежащим ей.
Найдется ли в оставшемся графе с пятью вершинами треугольник с одноцветными сторонами? Если найдется, то он содержится и в исходном графе.
В противном случае получается пятиугольник с красными сторонами и синими диагоналями. Теперь восстановим шестую вершину с ее ребрами.
Если ребро или ребро будет окрашено в красный цвет, то
образуется еще минимум один треугольник с красными сторонами или .
Если оба эти ребра будут синего цвета, то появится треугольник с синими сторонами. Вывод нетрудно перевести с языка теории графов на язык задачи.
Установлено свойство графа, являющееся обобщением свойства 2.
Свойство 4. В любом полном графе с шестью или более вершинами и ребрами одного из двух цветов всегда найдутся два разных треугольника с одноцветными сторонами. Эти два треугольника могут иметь общую вершину или даже общее ребро.
Если два треугольника имеют общую вершину или ребро, то их называют сцепленными.
Рассмотрим свойства полного графа, ребра которого окрашены в один из трех цветов, каждый цвет соответствует одному из трех отношений между объектами заданного множества.
Задача 4. Каждый из семнадцати ученых переписывается с остальными. В их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Нужно доказать, что не менее трех ученых переписываются друг с другом по одной и той же теме.
Решение. Условию задачи соответствует полный граф с семнадцатью вершинами и ребрами трех цветов. Из каждой вершины выходит шестнадцать ребер. Докажем, что в таком графе найдется хотя бы один треугольник с одноцветными сторонами. Заметим, что каждая вершина этого графа принадлежит хотя бы шести ребрам одного цвета. Пусть, например, вершина принадлежит шести красным ребрам.
Если среди вершин найдутся две, которые соединены красным ребром, то получится треугольник с красными сторонами. Если не найдутся, то все шесть вершин соединены между собой попарно ребрами двух цветов (зеленым и синим). Как было доказано ранее, в этом графе с шестью вершинами найдется хотя бы один треугольник либо с синими, либо с зелеными сторонами. Задача решена.
Сформулируем теперь свойство, доказанное при решении этой задачи.
Свойство 5. В полном графе с семнадцатью или более вершинами и ребрами трех цветов всегда найдется, по меньшей мере, один треугольник с одноцветными сторонами.
Заметим, что не случайно отношения, которые были найдены при решении задач, изображавшиеся цветными ребрами, симметричны, если - друг , то - друг , но не обязательно транзитивны, если - друг и - друг , то может и не быть другом . В случае, когда отношение между объектами было транзитивным, соответствующие ребра образовывали треугольник с одноцветными сторонами.
