Упр.4.11 ГДЗ Мерзляк Поляков 7 класс (Алгебра)
Рассмотрим вариант решения задания из учебника Мерзляк, Поляков 7 класс, Вентана-Граф: 4.11. В компании 10 человек. Можно ли утверждать, что все они являются одноклассниками, если каждый из них имеет в этой компании: 1) четыре одноклассника; 2) пять одноклассников?
Рассмотрим каждого человека как вершину графа, а связь «одноклассники» — как ребро.
Если каждый из 10 человек имеет в этой компании по 4 одноклассника, то можно построить граф, в котором у каждой вершины степень равна 4. Такой граф существует, значит, все 10 человек могут быть одноклассниками.
Если каждый из 10 человек имеет в этой компании по 5 одноклассников, то сумма степеней всех вершин равна
$$10 \cdot 5 = 50.$$
Но сумма степеней всех вершин графа должна быть чётной, так как она равна удвоенному числу рёбер. Число $$50$$ чётное, значит, препятствия нет. Однако для компании из 10 человек граф с одинаковой степенью 5 у каждой вершины существует, поэтому утверждать, что все они обязательно одноклассники, нельзя: это лишь одна из возможных ситуаций.
По рисунку видно, что в первом случае все 10 человек могут быть одноклассниками, а во втором — не обязательно.
Ответ
1) Да. 2) Нет.
