Лемма о рукопожатиях

Рассмотрим произвольного рыцаря пусть его друзья — это Пусть тогда если — один из врагов то враг для (по условию), то есть у хотя бы врага — противоречие.

Значит у каждого рыцаря не более друзей, а также у каждого рыцаря ровно врага, значит,

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

Разберём случаи:

1.

Берём две группы по рыцаря. Подграф на каждой из подгрупп — полный синий. Граф без учёта рёбер в группах — полный двудольный красный.

2.

Полный красный граф на вершинах.

3.

Но у каждого рыцаря по врага. Значит, не подходит.