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