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