171
правка
Изменения
Нет описания правки
|proof=
Для доказательства этой теоремы введём два определения.
{{Определение
|definition=
'''Простой (вершинно-простой) путь''' между двумя вершинами графа – путь между ними, в котором каждая из вершин графа встречается не более одного раза.
}}
{{Определение
|definition=
'''Длина пути''' – количество вершинрёбер, входящих в последовательность, задающую этот путь.
}}
Возьмём любой из существующих путей между нужными нам вершинами: <math>V_0E_1V_1E_2V_2 ... E_nV_n</math>.
Алгоритм:
Начнём процесс с вершины <math>V_0</math> и будем повторять его каждый раз для следующей вершины нового пути, пока не дойдём до последней. По построению, получившийся путь будет содержать каждую из вершин графа не более одного раза, а значит, будет простым.
Выберем из всех путей между данными вершинами путь наименьшей длины.
Тогда в нём содержатся две одинаковые вершины <math>V_i = V_j</math>, <math>i < j</math>. Удалим из исходного пути отрезок от <math>E_{i+1}</math> до <math>V_j</math>, включительно. Конечная последовательность также будет путём от <math>V_0</math> до <math>V_n</math> и станет короче исходной. Получено противоречие с условием: взятый нами путь оказался не кратчайшим. Значит, предположение неверно, выбранный путь – простой.
}}
==== Замечание ====
Так как вершинно-простой путь всегда является рёберно-простым, данная теорема справедлива и для рёберно-простого пути.
