Теорема на Менгер, алтернативно доказателство
Очевидно, ако [math]k[/math] върховете разделят [math]s[/math] и [math]t[/math] , тогава има най-много [math]k[/math] несвързани прости [math](s-t)[/math] пътища. Нека сега покажем, че ако [math]k[/math] от върховете на графиката разделят [math]s[/math] и [math]t[/math], тогава има [math]k[/math] несвързани прости [math](s-t)[/math] пътища. За [math]k=1[/math] това е очевидно. Нека за някои [math]k\gt 1[/math] това не е вярно. Вземете [math]h[/math] — най-малкото като [math]k[/math] и [math]F[/math] — графиката с най-малък брой върхове, за които теоремата не е вярна за избрания [math]h[/math]. Ще премахваме ръбове от [math]F[/math], докато получим [math]G[/math] така, че в [math]G[/math] [math]s[/math] и [math]t[/math] отделни [math]h[/math] върхове, а в [math]G-x[/math] [math]h-1[/math] връх, където [math]x[/math] е връх произволен ръб на графиката [math]G[/math] .
От дефиницията на [math]G[/math] следва, че за всеки от неговите ръбове [math]x[/math] има набор [math]S(x)[/math] от [math]h-1[/math] върхове, който в [math]G-x[/math] разделя [math]s[/math] и [math]t[/math] . Освен това графиката [math]G-S(x)[/math] съдържа поне една [math](s-t)[/math] верига, тъй като графиката [math]G[/math] има [math]h[/math] върхове, които разделят [math]s[/math] и [math]t[/math] в [math]G[/math] . Всяка такава [math](s-t)[/math] пътека трябва да съдържа край [math]x=uv[/math] , тъй като не е път в [math]G-x[/math] . Така [math]u,v \notin S(x)[/math] и ако [math]u \neq s,t [/math] тогава [math]S(x) \cup[/math] разделя [math]s[/math] и [math]t[/math] в [math]G[/math] .
Нека [math]W[/math] е произволен набор от [math]h[/math] върхове, които разделят [math]s[/math] и [math]t[/math] в [math]G[/math] .
Верига, свързваща [math]s[/math] сЧрез някакъв връх [math]w_i \in W[/math] и несъдържащ други върхове от [math]W[/math] ще наречем [math](s-W)[/math] верига. Нека наречем веригата [math](W-t)[/math] по подобен начин. Означете наборите от всички [math](s-W)[/math] и [math](W-t)[/math] вериги [math]P_s[/math] и [math]P_t[/math] съответно. Тогава всяка верига [math](s-t)[/math] започва с елемент от [math]P_s[/math] и завършва с елемент от [math]P_t[/math], тъй като всяка верига съдържа връх от [math]W[/math] . Общите върхове на пътеки от [math]P_s[/math] и [math]P_t[/math] принадлежат на набора [math]W[/math], тъй като поне един път от всеки набор от [math]P_s[/math] и [math]P_t[/math] съдържа (всеки) връх [math]w_i[/math] и ако имаше някакъв връх, който не принадлежи на набора [ma th]W[/math] , но се съдържа непосредствено и във [math](s-W)[/math] и във [math](W-t)[/math] вериги, тогава ще има [math](s-t)[/math] верига, която няма върхове от [math]W[/math] . И накрая, или [math]P_s-W=[/math], или [math]P_t - W=[/math], защото в противен случай или [math]P_s[/math] заедно с [math]\[/math] ребра или [math]P_t[/math] заедно с [math]\[/math] ребра образуват свързани графики с по-малко върхове от [math]G[/math], в които [ math]s [/math] и [math]t[/math] не са съседни и следователно всеки от тях има [math]h[/math] непресичащи се [math](s-t)[/math] вериги. Комбинирайки [math](s-W)[/math] и [math](W-t)[/math] части от тези вериги, ние образуваме в графиката [math]G[/math] [math]h[/math] несвързани [math](s-t)[/math] вериги. Стигнахме до противоречие. Твърдението е доказано.
Нека [math]P=\[/math] е най-краткият [math](s-t)[/math] път в [math]G[/math], [math]u_1u_2=x[/math] . Обърнете внимание, че от лема (I) [math]u_1 \neq t[/math] Формираме множеството[math]S(x)=\\>[/math] , което разделя върховете [math]s[/math] и [math]t[/math] в [math]G-x[/math] . Лема (I) предполага, че [math]u_1t \notin G[/math] . Използвайки лема (II) и вземайки [math]W=S(x)\cup [/math] , получаваме [math]\forall i \; sv_i \in G[/math] . Така, по Лема (I) [math]\forall i \; v_it \notin G[/math] . Ако обаче изберем [math]W=S(x) \cup [/math] , тогава чрез лема (II) получаваме [math]su_2 \in G[/math] , което противоречи на избора на [math]P[/math] като най-късата [math](s-t)[/math] верига. От полученото противоречие следва, че графиката [math]G[/math], удовлетворяваща посочените условия, не съществува и следователно няма графика [math]F[/math], за която теоремата да не е вярна.