Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 85, §19
№125. Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.
Дано:
6 вершин со степенями 1, 1, 2, 2, 3, 3
Найти:
два неодинаковых графа с такими вершинами
Сумма степеней чётная, значит, рёбер будет и такой граф существует (вершин нечётной степени — четыре, их число чётно). Нужно придумать два графа с шестью рёбрами, у которых вершины соединены по-разному. Подпишем вершины буквами А, Б, В, Г, Д, Е; рядом с каждой в скобках записана её степень.
Граф 1. Возьмём четырёхугольник АВБГ с диагональю АБ — это два треугольника с общей стороной АБ (5 рёбер). Степени А и Б равны 3, В и Г — по 2. Отдельно проведём ребро ДЕ: у вершин Д и Е степень 1. Всего рёбер .
Граф 2. Нарисуем треугольник АБВ, из вершины А проведём ребро АГ, а из Г — два ребра ГД и ГЕ («вилка»). Степени: А — 3 (АБ, АВ, АГ), Г — 3 (ГА, ГД, ГЕ), Б и В — по 2, Д и Е — по 1. Рёбер: АБ, БВ, ВА, АГ, ГД, ГЕ — шесть.
У обоих графов набор степеней один и тот же: 3, 3, 2, 2, 1, 1. Но графы неодинаковы. Например, в графе 1 две вершины степени 1 (Д и Е) соединены между собой ребром, а в графе 2 вершины степени 1 (Д и Е) друг с другом не соединены: у каждой из них единственный сосед — вершина Г. Такое различие нельзя убрать «движением вершин»: соединены ли две вершины ребром, от этого не зависит. Кроме того, граф 1 состоит из двух отдельных частей, а граф 2 — из одной.
Замечание. Среди графов без петель и повторяющихся рёбер с такими степенями всего пять неодинаковых (это проверяется перебором); мы выбрали два из них.
Ответ: Например, граф 1 (два треугольника с общим ребром и отдельное ребро) и граф 2 (треугольник с ребром и «вилкой»), см. рисунок; графы неодинаковы: в первом две вершины степени 1 соединены ребром, во втором нет.
