171
правка
Изменения
Нет описания правки
{{Теорема
|statement=
Если между двумя [[Основные определения теории графов|вершинами графа ]] существует [[Основные определения теории графов|путь]], то между ними существует простой путь.
|proof=
Для доказательства этой теоремы введём два определения.
{{Определение
|definition=
'''Простой (вершинно-простой) путь''' между двумя вершинами графа – [[Основные определения теории графов|путь ]] между ними, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Длина пути''' – количество [[Основные определения теории графов|рёбер]], входящих в последовательность, задающую этот путь.
}}
}}
==== Замечание ==Замечания ==
* Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого пути.
* Теорема может быть сформулирована как для [[Основные определения теории графов|ориентированного]], так и для [[Основные определения теории графов|неориентированного]] графа.
