Изменения

Перейти к: навигация, поиск

Теорема Менгера

2 байта убрано, 07:00, 11 октября 2010
фикс форматирования
Из определения G следует, что для всякого его ребра x существует множество <math>S(x)</math> из <math>h-1</math> вершин, которое в <math>G-x</math> разделяет s и t. Далее, граф <math>G-S(x)</math> содержит по крайней мере одну (s-t) цепь, так как граф G имеет h вершин, разделяющих s и t в G. Каждая такая (s-t) цепь должна содержать ребро <math>x=uv</math>, поскольку она не является цепью в <math>G-x</math>. Поэтому <math>u,v \notin S(x)</math>, и если <math>u <> s,t </math> то <math>S(x) \cup {u}</math> разделяет s и t в G
{{Лемма
Анонимный участник

Навигация