В некотором графе 11 рёбер. Пять вершин имеют степень 2, а остальные вершины — степень 3. Сколько вершин степени 3 содержит граф?

Question

Вопрос:

В некотором графе 11 рёбер. Пять вершин имеют степень 2, а остальные вершины — степень 3. Сколько вершин степени 3 содержит граф?

Фотография

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

Accepted Answer

Для решения задачи воспользуемся «леммой о рукопожатиях»: сумма степеней всех вершин графа равна удвоенному количеству его рёбер. 1. Найдём сумму степеней всех вершин. По условию в графе 11 рёбер, значит: $\sum_{v \in V} \text{deg}(v) = 2 \cdot 11 = 22$ 2. Пусть $x$ — количество вершин степени 3. Известно, что 5 вершин имеют степень 2. Тогда сумма степеней всех вершин выражается уравнением: $5 \cdot 2 + x \cdot 3 = 22$ 3. Решим полученное уравнение: $10 + 3x = 22$ $3x = 22 - 10$ $3x = 12$ $x = 4$ **Ответ: 4**.

В некотором графе 11 рёбер. Пять вершин имеют степень 2, а остальные вершины — степень 3. Сколько вершин степени 3 содержит граф?

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

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