B11. а) Существует ли граф, у которого сумма степеней всех вершин равна 365? б) В некотором графе сумма степеней всех вершин равна 168. Сколько в этом графе рёбер?

Решение:

Теорема о сумме степеней: Сумма степеней всех вершин любого графа равна удвоенному числу его рёбер. \( \sum_{i=1}^{n} \text{deg}(v_i) = 2|E| \), где \( |E| \) — число рёбер.

Следовательно, сумма степеней всех вершин всегда является чётным числом.

а) Существует ли граф, у которого сумма степеней всех вершин равна 365?

Число 365 — нечётное. Согласно теореме о сумме степеней, сумма степеней вершин графа не может быть нечётной. Следовательно, такой граф не существует.

б) В некотором графе сумма степеней всех вершин равна 168. Сколько в этом графе рёбер?

Используем теорему о сумме степеней: \( \text{Сумма степеней} = 2 \times \text{Число рёбер} \).

\( 168 = 2 \times |E| \)

Чтобы найти число рёбер, разделим сумму степеней на 2:

\( |E| = \frac{168}{2} = 84 \)

Ответ: а) Нет, такой граф не существует, так как сумма степеней вершин должна быть чётным числом. б) В этом графе 84 ребра.