В графе 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 вершин корректен не только арифметически, но и конструктивно.

Если хотите, могу привести пример конкретного набора ребер для такого графа.