Mutual-worst edge in stable matchings

If the endpoints of an edge rank one another last and one stable matching in a bipartite graph contains that edge, every stable matching contains it. In the symmetric difference of two stable matchings, preference comparisons propagate along alternating paths: if a vertex prefers its new partner, that partner must prefer its old partner to avoid blocking the old matching. An alternating path cannot end unmatched on the preferred side, so the component is an alternating cycle, on which the two parts prefer opposite matchings. A mutual-worst edge absent from the new matching would make both its endpoints prefer the new matching, contradicting this propagation.