Изменения

Предположим, что в <tex> G_f </tex> существует путь из <tex> s </tex> в <tex> t </tex>. И Из [[Теорема о существовании простого пути в случае существования пути#Теорема о существовании простого пути в случае существования пути|теоремы о существования простого пути]] следует, что в <tex> G_f </tex> также существует и простой путь из <tex> s </tex> в <tex> t </tex>. Тогда пусть <tex> p = \left \langle v_0, v_1, \dots, v_k \right \rangle </tex> {{---}} простой путь, где <tex> v_0 = s </tex> и <tex> v_k = t </tex>. Раз А раз <tex> p </tex> простой, то <tex> k < \left\vert V \right\vert </tex>. Поскольку <tex> h </tex> {{---}} функция высоты, то <tex> \forall i \in \{0, 1, \dots, k - 1 \} </tex> справедливо <tex> h(v_i) \leqslant h(v_{i+1}) + 1 </tex>. Следовательно, <tex> h(s) \leqslant h(t) + k </tex>. А так как по определению функции высоты <tex> h(t) = 0 </tex>, то <tex> h(s) \leqslant k < \left\vert V \right\vert </tex>, что противоречит условию, что <tex> h(s) = \left\vert V \right\vert </tex>.