Нарисовать граф с 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-цветный.