Изменения

Пусть <tex>P=\{s, u_1, u_2 ... t\}</tex> {{---}} кратчайшая <tex>(s-t)</tex> цепь в <tex>G</tex>, <tex>u_1u_2=x</tex>. Заметим, что из [[#lemma_1 | леммы (I) ]] <tex>u_1 \neq t</tex> Образуем множество <tex>S(x)=\{v_1, ... , v_{h-1}\}</tex>, разделяющее в <tex>G-x</tex> вершины <tex>s</tex> и <tex>t</tex>. Из [[#lemma_1 | леммы (I) ]] следует, что <tex>u_1t \notin G</tex>. Используя [[#lemma_2 | лемму (II) ]] и беря <tex>W=S(x)\cup {u_1}</tex>, получаем <tex>\forall i \; sv_i \in G</tex>. Таким образом в силу [[#lemma_1 | леммы (I) ]] <tex>\forall i \; v_it \notin G</tex>. Однако, если выбрать <tex>W=S(x) \cup {u_2}</tex>, то в силу [[#lemma_2 | леммы (II) ]] получим <tex>su_2 \in G</tex>, что противоречит выбору <tex>P</tex> как кратчайшей <tex>(s-t)</tex> цепи. Из полученного противоречия следует, что графа <tex>G</tex>, удовлетворяющего указанным условиям не существует, а значит не существует и графа <tex>F</tex>, для которого теорема не верна.

==Смотри См. также==