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

Ответ: 9 рёбер.

Обоснование:

• одна вершина изолирована, её степень = 0;
• остальные шесть вершин имеют степень 3, итого сумма степеней = 6·3 = 18.
• число рёбер равно половине суммы степеней: m = 18/2 = 9.

Пример построения: возьмём вершины {1,2,3,4,5,6,7}, сделаем вершину 7 изолированной и соединим все пары между частями {1,2,3} и {4,5,6} (полный двудольный граф K3,3). Рёбра: (1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6). У каждой из вершин 1–6 степень 3, вершина 7 — степень 0.