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

Пусть количество вершин степени 4 равно x. Тогда количество вершин степени 7 равно 2x.

Сумма степеней всех вершин равна удвоенному числу рёбер в графе. Это утверждение называется леммой о рукопожатиях.

Общая сумма степеней всех вершин: 4x + 7(2x) = 4x + 14x = 18x.

Удвоенное количество рёбер: 2 * 54 = 108.

Составляем уравнение: 18x = 108.

Решаем уравнение:

x = 108 / 18 = 6.

Количество вершин степени 4 равно 6, а количество вершин степени 7 равно 2 * 6 = 12.

Общее количество вершин в графе: 6 + 12 = 18.