Нарисовать граф с 5 вершинами и 9 ребрами

Задача: нарисовать граф с 5 вершинами и 9 ребрами. Ключевые идеи - Для простого графа на 5 вершинах максимум ребер равно C(5,2) = 10. - Чтобы получить 9 ребер, можно взять полный граф K5 и удалить одно ребро. Такой граф называется K5 минус одно ребро. - Пример: удалим ребро между вершинами A и B. Что именно получится - Вершины: A, B, C, D, E. - Ребра (все пары вершин, кроме AB): AC, AD, AE, BC, BD, BE, CD, CE, DE. Всего 9 ребер. Пошаговое объяснение 1) Начинаем с пяти вершин: A, B, C, D, E. 2) Добавляем все возможные ребра между ними (это будет K5, 10 ребер). 3) Удаляем одно ребро, например AB. Теперь осталось 9 ребер. 4) Проверяем свойства: - Степени вершин: - deg(A) = 3 (соединён с C, D, E) - deg(B) = 3 (соединён с C, D, E) - deg(C) = 4 (соединён с A, B, D, E) - deg(D) = 4 (соединён с A, B, C, E) - deg(E) = 4 (соединён с A, B, C, D) - Сумма степеней = 2 · 9 = 18, что согласуется. - Граф остаётся связным. - Цветовость: граф можно раскрасить в 4 цвета (например, A и B одной краской, C, D, E — тремя другими цветами). Следовательно, хроматическое число равно 4. Как изобразить на рисунке - Вершины обозначьте на листе пятью точками: A, B, C, D, E. - Соедините все пары вершин, кроме пары A и B. - Конкретный список ребер можно записать так: AC, AD, AE, BC, BD, BE, CD, CE, DE. - Пример расположения вершин можно выбрать произвольно, главное — не забыть, что AB не соединено. Альтернативные представления - Матрица смежности (порядок вершин A, B, C, D, E): 0 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 - Контрольная проверка: если заменить AB на существующее ребро, получите K5 (10 ребер); если же убрать другое ребро, останется 9 ребер, но структура будет аналогичной по характеру. Итого - Граф с 5 вершинами и 9 ребрами можно получить как K5 минус одно ребро, например AB. Edge set: {AC, AD, AE, BC, BD, BE, CD, CE, DE}. Степени вершин: (3, 3, 4, 4, 4). Граф связный и 4-цветный.