Паросочетание: различия между версиями

|страницы=133–138

|год=1959}}</ref>.

 

*Если ''A'' и ''B'' — два максимальных паросочетания, то |''A''| ≤ 2|''B''| и |''B''| ≤ 2|''A''|. Чтобы это увидеть, заметьте, что каждое ребро из ''B'' \ ''A'' может быть сопряжено максимум двум рёбрам из ''A'' \ ''B'' поскольку ''A'' — паросочетание. Однако каждое ребро ''A'' \ ''B'' сопряжено с ребром ''B'' \ ''A'' ввиду того, что ''B'' — максимальное. Следовательно,