73. 3. Построить граф из 8 вершин, в котором 4 вершины с нечетной степенью (без петель)

Пояснение:

Задание требует построить граф с определёнными условиями. В графе должно быть 8 вершин. Из них ровно 4 вершины должны иметь нечетную степень. Также граф должен быть без петель (без рёбер, соединяющих вершину саму с собой).

Принцип решения:

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

В данном задании требуется, чтобы 4 вершины имели нечетную степень. Это возможно, так как 4 — число чётное.

Пример построения:

Для построения такого графа можно использовать следующую стратегию:

1. Возьмем 4 вершины (назовем их A, B, C, D), которым нужно придать нечетную степень.
2. Соединим их между собой рёбрами так, чтобы каждая из них имела степень 1 или 3 (или любую другую нечетную степень). Например, можно соединить A-B, C-D, A-C. В этом случае степени будут: deg(A)=2, deg(B)=1, deg(C)=2, deg(D)=1. Пока две вершины с нечетной степенью.
3. Добавим оставшиеся 4 вершины (E, F, G, H) и соединим их так, чтобы они имели чётную степень (например, 0 или 2).
4. Теперь нужно довести степень вершин A, B, C, D до нечетной. Если мы их соединим так: A-B, C-D, A-C, B-D. Тогда степени будут: deg(A)=2, deg(B)=2, deg(C)=2, deg(D)=2. Это не подходит.
5. Попробуем иначе: Соединим 4 вершины (A, B, C, D) в полный граф K₄. Степени вершин будут: deg(A)=3, deg(B)=3, deg(C)=3, deg(D)=3. Теперь у нас 4 вершины с нечетной степенью (3).
6. Оставшиеся 4 вершины (E, F, G, H) можно оставить изолированными (степень 0, что является чётной степенью).

Визуализация (описание):

Представьте 8 точек на плоскости. Четыре из них (A, B, C, D) образуют квадрат, и к каждой вершине квадрата проведена диагональ, соединяющая противоположные вершины (A с C, B с D). Остальные четыре точки (E, F, G, H) находятся отдельно от этого квадрата, не соединенные ни с чем.

Итоговый граф:

• Вершины: {A, B, C, D, E, F, G, H}
• Рёбра: {(A, B), (A, C), (A, D), (B, C), (B, D), (C, D)}
• Степени вершин:
• deg(A) = 3 (нечетная)
• deg(B) = 3 (нечетная)
• deg(C) = 3 (нечетная)
• deg(D) = 3 (нечетная)
• deg(E) = 0 (четная)
• deg(F) = 0 (четная)
• deg(G) = 0 (четная)
• deg(H) = 0 (четная)

Ответ: Граф, состоящий из полного графа K₄ (4 вершины с нечетной степенью 3) и 4 изолированных вершин (с четной степенью 0).