Упр.71 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Задача

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 71. На лавке сидят семеро ребят. Каждый имеет среди остальных не менее трёх братьев. Докажите, что все семеро — братья.

Подробный ответ

Рассмотрим граф, в котором вершины — это семеро ребят, а ребро соединяет двух ребят тогда и только тогда, когда они братья.

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

Предположим, что не все семеро — братья. Тогда в графе есть хотя бы одна пара ребят, не соединённых ребром. Рассмотрим любого из них. У него не менее трёх братьев среди оставшихся шести ребят, значит среди семи вершин он соединён как минимум с тремя.

Если бы существовали две не связанные между собой вершины, то каждая из них должна была бы быть соединена как минимум с тремя из остальных пяти вершин. Но тогда среди семи вершин невозможно избежать появления общей группы, в которой каждый связан со всеми остальными: при числе вершин $$7$$ и минимальной степени $$3$$ дополнение к графу имеет степень не более $$3$$, а значит не может содержать разбиение на несколько несвязанных частей без нарушения условия.

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