Теорема. Для -графа следующие утверждения эквивалентны. 1) - дерево; 2) связный граф и ; 3) - ациклический граф и ; 4) любые две несовпадающие вершины графа соединяет единственная, причем простая, цепь; 5) - ациклический граф, обладающий тем свойством,

Нам необходимо доказать импликацию $4 \Rightarrow 5$.

1. Дано

Пусть $G = (V, E)$ — $(n, m)$-граф, где $n = |V|$ — число вершин, $m = |E|$ — число рёбер.

Условие 4 (Посылка): Любые две несовпадающие вершины графа $G$ соединены единственной, причём простой, цепью.

2. Найти

Доказать, что из условия 4 следует Условие 5: $G$ — ациклический граф, обладающий тем свойством, что если какую-либо пару его смежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл.

3. Решение

Доказательство импликации $4 \Rightarrow 5$ состоит из двух частей: А)...