質問: グラフ理論において、安定結婚問題があります。 ある2部グラフの特定の安定マッチングにおいて、ペアを作れなかった人(たとえば男性数>女性数でのマッチングで存在)は、どのような安定マッチングにおいてもペアが作れないことを、安定結婚問題における「絶望の定理」と呼ぶらしいのですが、この定理の証明を見つけられずにいます。 証明自体、もしくは証明のソースをご存知の方はいらっしゃいますでしょうか。
回答: @argus さんの情報を情報をもとに、調べて行った結果、 (man-oriented な Gale-Shapley で man-optimal (最大元)かつ woman-pessimal (最小元)が得られる) と (1. optimal, 任意の matching, pessimal の3つの間で、パートナーの有無は、単調増加(語弊あり?)する 2. ある参加者のパートナーの有無が stable matching 間で変わったとすると、1. の結果から玉突き事故のようなことが起こってしまうので、そんなことは起こらない) によって、説明できそうでした。