В графе 16 рёбер. Каждая вершина графа имеет или степень 3, или степень 5. Причём вершин степени 3 столько же, сколько вершин степени 5. Сколько вершин в этом графе?

Ответ: 8 вершин. Пошаговое решение 1) Пусть a — число вершин степени 3, b — число вершин степени 5. По условию a = b. 2) Сумма степеней вершин равна удвоенному числу ребер: 2|E| = 2·16 = 32. 3) Сумма степеней по вершинам равна 3a + 5b. Так как a = b, получаем 3a + 5a = 8a. 4) Отсюда 8a = 32, значит a = 4. Следовательно, b = 4. 5) Общее число вершин n = a + b = 4 + 4 = 8. 6) Проверка на корректность: средняя степень = сумма степеней / n = 32 / 8 = 4, что разумно, ведь вершины имеют степени 3 или 5. Дополнительный комментарий по существованию графа - Последовательность степеней (5, 5, 5, 5, 3, 3, 3, 3) удовлетворяет критерию графичности (например, по алгоритму Хавела–Хакки эта последовательность сводится к нулям без конфликтов), значит такой граф действительно существует. Таким образом, ответ 8 вершин корректен не только арифметически, но и конструктивно. Если хотите, могу привести пример конкретного набора ребер для такого графа.