4 Может ли количество вершин нечетной степени в каком-то графе ровняться:

Решение:

Согласно теореме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному количеству ребер. Это означает, что сумма степеней всегда является четным числом. Из этого следует, что количество вершин с нечетной степенью в любом графе всегда четно.

• а) 0: Да, может. Например, граф, где все вершины имеют четную степень (например, цикл).
• б) 1: Нет, не может. Число вершин с нечетной степенью всегда четно.
• в) 2: Да, может. Например, граф с двумя вершинами, соединенными одним ребром.
• г) 4: Да, может. Например, полный граф K₅ имеет 5 вершин, каждая из которых имеет степень 4 (четная). Полный граф K₄ имеет 4 вершины, каждая из которых имеет степень 3 (нечетная).

Ответ: а) 0 — Да; б) 1 — Нет; в) 2 — Да; г) 4 — Да.