12
правок
Изменения
Нет описания правки
{{Теорема
|statement=
Для графа <texmath>G</texmath> следующие утверждения эквивалентны:1) <texmath>G</texmath> - дерево;
2) любые две вершины в <texmath>G</texmath> соединены единственной простой цепью;
3) <texmath>G</texmath> связный граф и <texmath>p = q + 1</texmath>;
4) <texmath>G</texmath> ациклический граф и <texmath>p = q + 1</texmath>;
5) <texmath>G</texmath> - ациклический граф, и если любую праву несмежных вершин соединить ребром <tex>x</tex>, то в графе <texmath>G + x</texmath> будет точно один простой цикл;
6) <tex>G</tex> - связный граф, отличный от K<sub>p</sub> для p <tex>p \ge 3</tex>3, и если любую пару несмежных вершин соединить ребром <tex>х</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл;
7) <tex>G</tex> - Граф, отличный от K<sub>3</sub> <tex>\cup</tex> K<sub>1</sub> и K<sub>3</sub><tex>\cup</tex> K<sub>2</sub>, <tex>p = q + 1</tex>, и если любую пару несмежных вершин соединить ребром <tex>x</tex>, то в графе <tex>G + x</tex> будет точно один простой цикл.Б.
|proof=
