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

Решение:

Связный граф — это граф, в котором между любыми двумя вершинами существует путь. Для построения связного графа из 6 вершин и 7 рёбер можно начать с минимального связного графа (остовного дерева), а затем добавить оставшиеся рёбра.

Минимальное связное количество рёбер для 6 вершин равно 5 (чтобы каждая вершина была связана с другими). Нам нужно добавить ещё 7 - 5 = 2 ребра.

Пример построения:

1. Возьмем 6 вершин, обозначим их цифрами от 1 до 6.
2. Построим остовное дерево (например, цепь): 1-2, 2-3, 3-4, 4-5, 5-6. Это 5 рёбер, и граф связный.
3. Добавим ещё 2 ребра, чтобы получить 7 рёбер, сохраняя связность. Например, добавим ребро 1-3 и ребро 4-6.

Ответ: Граф с вершинами {1, 2, 3, 4, 5, 6} и рёбрами {(1,2), (2,3), (3,4), (4,5), (5,6), (1,3), (4,6)} является связным и содержит 6 вершин и 7 рёбер.