Цветные графы

[Stensen]

Доброго всем времени суток. Помогите понять решение задачи.
В городе $N$ жителей. Любые двое из них либо дружат, либо враждуют. Каждый день не более чем один из них может начать новую жизнь: поссориться со всеми друзьями и подружиться со всеми врагами. Известно, что любые три жителя могут подружиться. Доказать, что все жители могут подружиться.

Решение автора. "Каждому жителю поставим в соответствие вершину графа. Пусть синее ребро означает, что двое дружат, а красное — что не дружат. Получим граф с $N$ вершинами и ребрами двух цветов, который можно подвергать следующим преобразованиям: выбирать вершину и все красные ребра, которым она принадлежит, перекрашивать в синие, а все синие — в красные. По условию каждый треугольник может стать синим, то есть в графе могут быть только или треугольники с синими сторонами, или треугольники, у которых одна сторона синяя и две — красные"

- Здесь не понятно, почему не может быть красного треугольника или с двумя синими и одной красной сторонами? В условии про это ничего не сказано.

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

- Здесь тоже не понятно. Если возьмем вершину, красная степень которой меньше синей и перекрасим, синих ребер станет меньше.

[provincialka]

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

Stensen в сообщении #1406321 писал(а):

Если возьмем вершину, красная степень которой меньше синей и перекрасим

Зачем? В решении говорится об обратном случае.
Там сомнение в другом: что всегда есть вершина "более красная, чем синяя". Надо подумать.

[12d3]

Stensen в сообщении #1406321 писал(а):

В любом таком графе найдется вершина, красная степень которой больше синей.

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

[Stensen]

12d3 в сообщении #1406347 писал(а):

Stensen в сообщении #1406321 писал(а):

В любом таком графе найдется вершина, красная степень которой больше синей.

Вот это утверждение не слишком очевидное, хотя несложно доказываемое.

Рассмотрим некоторое красное ребро $(A,B)$. Т.к. граф полный, степень каждой вершины $N-1$. Пусть синяя степень вершины $A$ больше красной, $A_{BLU}>\frac{N-1}{2}$ и рассмотрим все вершины $C_i$, соединенные синими ребрами с $A$, т.е. все ребра $(A,C_i) $ синие. Если считаем, что нет треугольников с двумя синими ребрами (согласно автору), то в треугольниках $(A,B,C_i)$ все ребра $(B,C_i)$ красные, которых столько же сколько синих ребер у вершины $A$, за исключением $(A,B) $, т.е. больше половины.

Если есть треугольники с двумя синими сторонами, то это доказательство не подойдет, но не понимаю, почему таких треугольников нет (согласно автору)?

provincialka в сообщении #1406329 писал(а):

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

Если перекрашиваем все ребра вершины, которая содержит треугольник с двумя синими ребрами, то получим такой же треугольник или весь красный. Пока не понимаю, что мне дает четность?

[Someone]

Stensen в сообщении #1406429 писал(а):

Если есть треугольники с двумя синими сторонами, то это доказательство не подойдет, но не понимаю, почему таких треугольников нет (согласно автору)?

А могут ли соответствующие три жителя подружиться?

[Stensen]

Someone в сообщении #1406441 писал(а):

Stensen в сообщении #1406429 писал(а):

Если есть треугольники с двумя синими сторонами, то это доказательство не подойдет, но не понимаю, почему таких треугольников нет (согласно автору)?

А могут ли соответствующие три жителя подружиться?

Спасибо, понял. Возможны только авторские треугольники.