В некотором графе 4 вершины и 8 рёбер. Две вершины имеют степень 5, третья вершина - степень 4. Какова степень четвёртой вершины?

Решение:

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

В данном графе 4 вершины и 8 рёбер.

Пусть степени вершин равны \( d_1, d_2, d_3, d_4 \).

Сумма степеней: \( d_1 + d_2 + d_3 + d_4 = 2 × 8 = 16 \).

Известно, что две вершины имеют степень 5, а третья — степень 4.

Пусть \( d_1 = 5 \), \( d_2 = 5 \), \( d_3 = 4 \). Тогда:

\( 5 + 5 + 4 + d_4 = 16 \)

\( 14 + d_4 = 16 \)

\( d_4 = 16 - 14 \)

\( d_4 = 2 \)

Степень четвёртой вершины равна 2.

Ответ: 2