Построй граф, в котором 8 вершин: три из них изолированные, а каждая из оставшихся вершин соединена с четырьмя другими. Сколько рёбер в этом графе?

Решение:

Всего в графе 8 вершин.

1. Три вершины являются изолированными, то есть они не соединены ни с одной другой вершиной.
2. Оставшихся вершин: 8 - 3 = 5.
3. Каждая из этих 5 вершин соединена с четырьмя другими.
4. Согласно лемме о рукопожатиях (теорема о сумме степеней вершин), сумма степеней всех вершин графа равна удвоенному числу рёбер.
5. Степень каждой из 5 вершин равна 4. Сумма их степеней: 5 вершин * 4 = 20.
6. Степень каждой из 3 изолированных вершин равна 0. Сумма их степеней: 3 вершины * 0 = 0.
7. Общая сумма степеней всех вершин: 20 + 0 = 20.
8. Число рёбер (E) равно половине суммы степеней: \( E = \frac{20}{2} \).

Ответ: 10.