3. На рисунке изображён граф. а) Найдите степень вершины С? б) Выпишите вершины нечетной степени. в) Сколько вершин в этом графе имеют наименьшую степень? Выпишите их.

Решение:

а) Вершина C соединена с вершинами H, B, E, D. Ее степень равна 4.

б) Степени всех вершин:

• deg(H) = 3 (соединения с N, F, C)
• deg(N) = 3 (соединения с H, F, B)
• deg(A) = 2 (соединения с N, B)
• deg(B) = 3 (соединения с N, A, C, D)
• deg(C) = 4 (соединения с H, B, E, D)
• deg(E) = 2 (соединения с H, C, D)
• deg(D) = 2 (соединения с B, C, E)
• deg(F) = 2 (соединения с H, N)

Вершины с нечетной степенью: H (3), N (3), B (3).

в) Наименьшая степень в этом графе равна 2. Вершины с наименьшей степенью: A, E, D, F.

Ответ: а) deg(C) = 4; б) H, N, B; в) 4 вершины: A, E, D, F.