Номер 125, страница 85, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

125 Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями $1, 1, 2, 2, 3, 3$.

Задача состоит в том, чтобы найти и нарисовать два неизоморфных (то есть различных по структуре) графа, каждый из которых имеет 6 вершин со степенями 1, 1, 2, 2, 3, 3.

Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному числу его рёбер. В нашем случае сумма степеней составляет $1 + 1 + 2 + 2 + 3 + 3 = 12$. Это чётное число, что подтверждает возможность существования таких графов. Число рёбер в каждом графе будет равно $12 / 2 = 6$.

Таким образом, мы ищем два графа с 6 вершинами и 6 рёбрами, имеющие заданный набор степеней, но разную структуру.

Построим первый граф. Обозначим вершины $v_1, v_2, ..., v_6$. Пусть вершины $v_1, v_2$ имеют степень 3, вершины $v_3, v_4$ — степень 2, а вершины $v_5, v_6$ — степень 1. Соединим две вершины с наибольшей степенью ($v_1$ и $v_2$) между собой. Затем построим треугольник, соединив их с вершиной $v_3$. Оставшиеся рёбра распределим так, чтобы получить нужные степени. Набор рёбер: $(v_1, v_2), (v_1, v_3), (v_2, v_3), (v_1, v_5), (v_2, v_4), (v_4, v_6)$. Проверка степеней:

• $\deg(v_1) = 3$ (соседи: $v_2, v_3, v_5$)
• $\deg(v_2) = 3$ (соседи: $v_1, v_3, v_4$)
• $\deg(v_3) = 2$ (соседи: $v_1, v_2$)
• $\deg(v_4) = 2$ (соседи: $v_2, v_6$)
• $\deg(v_5) = 1$ (сосед: $v_1$)
• $\deg(v_6) = 1$ (сосед: $v_4$)

В этом графе две вершины максимальной степени 3 ($v_1$ и $v_2$) смежны. Также в графе присутствует цикл длины 3 (треугольник), образованный вершинами $v_1, v_2, v_3$.

Построим второй граф, структура которого будет отличаться. Главным отличием сделаем то, что две вершины с максимальной степенью 3 не будут соединены ребром. Пусть $v_1$ и $v_2$ — вершины степени 3. Соединим $v_1$ с вершинами $v_3, v_4, v_5$, а вершину $v_2$ — с вершинами $v_3, v_4, v_6$. Набор рёбер: $(v_1, v_3), (v_1, v_4), (v_1, v_5), (v_2, v_3), (v_2, v_4), (v_2, v_6)$. Проверка степеней:

• $\deg(v_1) = 3$ (соседи: $v_3, v_4, v_5$)
• $\deg(v_2) = 3$ (соседи: $v_3, v_4, v_6$)
• $\deg(v_3) = 2$ (соседи: $v_1, v_2$)
• $\deg(v_4) = 2$ (соседи: $v_1, v_2$)
• $\deg(v_5) = 1$ (сосед: $v_1$)
• $\deg(v_6) = 1$ (сосед: $v_2$)

В отличие от первого графа, здесь две вершины максимальной степени 3 ($v_1$ и $v_2$) не смежны. Этот граф не содержит треугольников; минимальный цикл имеет длину 4 (например, $v_1-v_3-v_2-v_4-v_1$). Отсутствие нечётных циклов означает, что этот граф является двудольным. Различия в смежности вершин с одинаковыми степенями и в структуре циклов доказывают, что графы неизоморфны.

Ниже представлены два неодинаковых графа, удовлетворяющих условию задачи. Вершины с одинаковыми степенями окрашены в один цвет: степень 3 — синий, степень 2 — зелёный, степень 1 — красный.

Граф 1 (смежные вершины степени 3, содержит треугольник)

Граф 2 (несмежные вершины степени 3, двудольный)