Изменения

Тогда между вершинами <tex>a</tex> и <tex>b</tex> есть простой путь <tex>P : P \land x = \varnothing</tex>. Составим такой путь <tex>Q</tex>, что <tex>Q = ((u \rightsquigarrow a ) \circ P \circ (b \rightsquigarrow w)) </tex>. Сделаем путь <tex>Q</tex> [[Теорема о существовании простого пути в случае существования пути|простым]]. Получим простой путь <tex>(u \rightsquigarrow w)</tex>, не проходящий по ребру <tex>x</tex>. Противоречие.

}}

==Источники информации==

* Харари Ф. Теория графов. М.: Мир, 1973. (Изд. 3, М.: КомКнига, 2006. — 296 с.)

[[Категория:Алгоритмы и структуры данных]]

[[Категория:Связность в графах]]