Алгоритм Куна для поиска максимального паросочетания

Теорема:

Если из вершины х не существует дополняющей цепи относительно паросочетание М, то если паросочетание М' получается из М изменением вдоль дополняющей цепи, то из х не существует дополняющей цепи в М'.

Доказательство:

[math]\triangleright[/math]

[

[math]\triangleleft[/math]