Есть множество точек некоторые из которых соединены линией одного из шести цветов.
Причем из каждой точки может выходить не более одной линии каждого цвета.
Какое минимальное количество точек надо взять чтобы из них можно было гарантированно выбрать пару не соединенных линией?
Спойлер:
7 точек.
Для начала покажем, что с указанными ограничениями рёбра полного 6-графа можно раскрасить в 6 цветов:
x12345
1x5436
25x163
341x52
4365x1
56321x
Если предположить, что мы смогли сделать это для полного 7-графа, то с одной стороны мы получим, что в каждой строке (как и в каждом столбце) ровно по одному числу от 1 до 6, а значит каждое число в этой таблице встречается ровно 7 раз.
Но из-за симметрии относительно главной диагонали, каждое число должно встречаться чётное число раз - противоречие.