4. У графа 5 вершин степени 4 и еще 3 вершин степени 6. Сколько ребер в этом графе?

Решение:

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

Сумма степеней вершин степени 4: 5 вершин * 4 = 20.

Сумма степеней вершин степени 6: 3 вершины * 6 = 18.

Общая сумма степеней всех вершин: 20 + 18 = 38.

Число ребер = Общая сумма степеней / 2 = 38 / 2 = 19.

Ответ: 19