Question

1) В графе 5 вершин, из каждой выходит 4 ребра. Сколько у него ребер? Нарисуйте такой граф. 2) Для каждого графа ответьте на вопросы: сколько у него вершин; сколько у него ребер; есть ли у него изолированные вершины.

Accepted Answer

1) Сумма степеней всех вершин равна двойному количеству рёбер (лемма о рукопожатиях). В данном графе каждая из 5 вершин имеет степень 4.
Сумма степеней: $5 	imes 4 = 20$.
Количество рёбер: $20 : 2 = 10$.
Такой граф называется полным ($K_5$), в нём каждая вершина соединена со всеми остальными.
Ответ: 10 рёбер.

2) Разбор представленных графов:

Граф №1
- Вершин: 5 (Д, Б, К, М, Р).
- Рёбер: 5 (Д-Б, Д-К, Б-К, Б-М, К-Р).
- Изолированные вершины: нет (из каждой вершины выходит хотя бы одно ребро).

Граф №2
- Вершин: 6 (1, 2, 3, 4, 5, 6).
- Рёбер: 5 (1-2, 1-4, 2-4, 2-6, 5-6).
- Изолированные вершины: есть, вершина 3 (к ней не ведёт ни одно ребро).

Ответ ассистента

Другие решения