Задача 4 (Теория графов 1)

Задача 4.

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

celebritycruise•-1, 23 Oct'15

Что значит три попарно соединенные вершины? Это значит, что между ними 3 ребра или 2?

Artem Kotelskiy•1719, 24 Oct'15

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

Чтобы послать решение задачи на проверку, или задать вопрос по условию, войдите на сайт под своим аккаунтом.