Изменения
→Доказательство корректности
Все мужчины и женщины будут заняты.
|proof=
Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда и некоторая женщина (<tex>a</tex>) не замужемнезамужняя. По [[#observation2|наблюдению 2]], <tex>a</tex> не получала предложений. Но <tex>A</tex> сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты.
Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
