Question

Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3. В некотором графе 6 вершин, степени которых равны: а) 2, 2, 3, 3, 4, 4; б) 0, 1, 2, 2, 3, 4. Сколько всего рёбер в этом графе?

Accepted Answer

1. Чтобы нарисовать граф с 5 вершинами и степенями 1, 2, 2, 3, 3, можно соединить их следующим образом:
- Пусть вершины будут A, B, C, D, E.
- Соединим: A-B, B-C, C-D, D-E, E-B, D-A (пример одного из вариантов).
В таком графе:
- Вершина с 1 ребром (степень 1)
- Две вершины с 2 ребрами (степень 2)
- Две вершины с 3 ребрами (степень 3)

2. Для решения воспользуемся леммой о рукопожатиях: сумма степеней всех вершин графа равна удвоенному количеству его рёбер ($2E = \sum deg(v)$).

а) Степени: 2, 2, 3, 3, 4, 4.
Сумма степеней: $2 + 2 + 3 + 3 + 4 + 4 = 18$.
Количество рёбер: $18 / 2 = 9$.
Ответ: 9.

б) Степени: 0, 1, 2, 2, 3, 4.
Сумма степеней: $0 + 1 + 2 + 2 + 3 + 4 = 12$.
Количество рёбер: $12 / 2 = 6$.
Ответ: 6.

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

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