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

Решение:

Обозначим количество вершин степени 3 как $$x$$, а количество вершин степени 5 как $$y$$.

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

• $$3x + 5y = 2 imes 17$$
• $$3x + 5y = 34$$

Также по условию, вершин степени 3 на 2 меньше, чем вершин степени 5:

• $$x = y - 2$$

Теперь подставим второе уравнение в первое:

• $$3(y - 2) + 5y = 34$$
• $$3y - 6 + 5y = 34$$
• $$8y = 34 + 6$$
• $$8y = 40$$
• $$y = 40 / 8$$
• $$y = 5$$

Теперь найдём $$x$$, используя $$x = y - 2$$:

• $$x = 5 - 2$$
• $$x = 3$$

Общее количество вершин в графе равно сумме вершин степени 3 и вершин степени 5:

• $$x + y = 3 + 5 = 8$$

Ответ: 8