Покажите, что не существует связного графа, в котором 8 вершин и 6 рёбер.
от

1 Ответ

Дано:

Связный граф с 8 вершинами и 6 рёбрами.

Найти:

Доказательство того, что такой граф не существует.

Решение:

Для связного графа с n вершинами необходимо, чтобы количество рёбер было не менее n - 1. Это связано с тем, что минимальная структура, обеспечивающая связность, - это дерево, у которого количество рёбер равно количеству вершин минус один.

В данном случае:
n = 8, следовательно, минимальное количество рёбер:
n - 1 = 8 - 1 = 7.

Поскольку у нас только 6 рёбер, это количество меньше минимально необходимого для связности графа.

Таким образом, граф с 8 вершинами и 6 рёбрами не может быть связным.

Ответ:
Не существует связного графа с 8 вершинами и 6 рёбрами.
от