5. Представь, что у тебя есть 6 друзей, и каждый из них может быть знаком с некоторыми другими. Можно ли построить граф, где вершины соответствуют людям, а ребра — знакомствам, чтобы у каждого человека было ровно 3 знакомых? Почему да или почему нет? Как это связано с понятием суммой степеней вершин?

Нет, такой граф построить нельзя.

Если у каждого из 6 человек ровно 3 знакомых, сумма степеней вершин была бы 6 · 3 = 18. Но в любом графе каждое ребро соединяет две вершины и учитывается в сумме степеней дважды, поэтому сумма степеней всегда чётная и равна удвоенному числу рёбер. Хотя 18 чётно, число рёбер тогда было бы 18 ÷ 2 = 9, что само по себе возможно; проверим условие внимательнее.

Действительно, граф существует: можно расположить 6 вершин по кругу и соединить каждую с двумя соседями, а затем соединить противоположные пары. Тогда степень каждой вершины равна 3, всего получается 9 рёбер.

Ответ: да. Например, цикл из 6 вершин с добавленными тремя рёбрами между противоположными вершинами. Сумма степеней равна 18, то есть удвоенному числу рёбер: 2 · 9.