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

Решение:

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

\( \sum_{v ∈ V} deg(v) = 2|E| \)

В данном графе:

• 7 вершин степени 4, их суммарная степень: \( 7 \times 4 = 28 \)
• 6 вершин степени 3, их суммарная степень: \( 6 \times 3 = 18 \)
• Общая сумма степеней всех вершин: \( 28 + 18 = 46 \)

Теперь найдем количество ребер:

\( 2|E| = 46 \)

\( |E| = \frac{46}{2} = 23 \)

Ответ: 23 ребра.