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

Question

Вопрос:

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

Фотография

Ответ ассистента

Accepted Answer

Для решения задачи воспользуемся леммой о рукопожатиях, которая гласит, что сумма степеней всех вершин графа равна удвоенному количеству рёбер: $\sum deg(v) = 2E$. Пусть $x$ — количество вершин степени 7. Тогда количество вершин степени 5 будет равно $x - 2$ (так как их на 2 меньше). Составим уравнение суммы степеней: $7x + 5(x - 2) = 2 \cdot 13$ $7x + 5x - 10 = 26$ $12x = 36$ $x = 3$ Количество вершин степени 7 равно 3. Количество вершин степени 5 равно $3 - 2 = 1$. Общее количество вершин: $3 + 1 = 4$. Ответ: 4

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

Ответ ассистента

Другие решения