После завершения алгоритма не будет неустойчивых пар.
|proof=
# Предположим A-b (A, B — мужчины; a, b — женщины; A женат на a, B женат на b) — нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли# . Рассмотрим два случая:1. # A не делал предложения b <tex> \Rightarrow</tex> A находит a ''более привлекательной'', чем b <tex> \Rightarrow</tex> A-b — устойчивая пара2. # A делал предложения b <tex> \Rightarrow</tex> b отказала A (сразу или на одной из последующих итераций) <tex> \Rightarrow</tex> b находит B ''более привлекательным'', чем A <tex> \Rightarrow</tex> A-b — устойчивая пара
}}
