|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 — устойчивая пара
}}
