7. Постройте несвязный граф из 6 вершин и 7 рёбер.

Задание 7

Чтобы построить несвязный граф из 6 вершин и 7 рёбер, мы можем создать несколько отдельных компонент связности.

Например, можно взять полный граф \( K_4 \) (4 вершины, 6 рёбер) и добавить две изолированные вершины (2 вершины, 0 рёбер). Это даст нам 6 вершин и 6 рёбер, но граф будет несвязным. Нам нужно 7 рёбер.

Другой вариант: создадим одну компоненту связности с 5 вершинами и 5 рёбрами (например, цикл \( C_5 \)), и ещё одну компоненту связности с 1 вершиной и 2 рёбрами. Это невозможно, так как одна вершина может иметь максимум 0 рёбер (петля — запрещена).

Давайте построим так: одну компоненту — полный граф \( K_4 \) (4 вершины, 6 рёбер). К одной из вершин \( K_4 \) добавим ещё одно ребро, ведущее к новой, 5-й вершине. Теперь у нас 5 вершин, 7 рёбер. Вершины 1, 2, 3 имеют степень 3, вершина 4 — степень 4, вершина 5 — степень 1. Оставшуюся 6-ю вершину сделаем изолированной.

Граф будет иметь:

• Вершины 1, 2, 3, 4, соединённые в \( K_4 \).
• Ребро между вершиной 4 и вершиной 5.
• Изолированная вершина 6.

Степени вершин:

• Вершины 1, 2, 3: степень 3 (нечётная).
• Вершина 4: степень 3 (от \( K_4 \)) + 1 (к вершине 5) = 4 (чётная).
• Вершина 5: степень 1 (нечётная).
• Вершина 6: степень 0 (чётная).

У нас 4 вершины с нечётной степенью (1, 2, 3, 5) и 2 вершины с чётной степенью (4, 6). Всего 6 вершин. Рёбер: 6 (в \( K_4 \)) + 1 (между 4 и 5) = 7.

Вершина 6 — изолированная. Компоненты связности: {1, 2, 3, 4, 5} и {6}. Граф несвязный.

Ответ: Граф построен.