Let $G=(V,E)$ be a graph and let for each $v\in V$ let $\le_v$ be a total order on $\delta(v)$. A matching $M\subseteq E$ is stable, if for every edge $e\in E$ there is $f\in M$, s.t. $e\le_v f$ for a common vertex $v\in e\cap f$
I'm looking at the proof of the stable marriage theorem - which states that every bipartite graph has a stable matching - in Schrijver's book on combinatorial optimization. It goes something like this.
Let $G=(V,E)$ be bipartit with bipartition $V=A\cup B$. For every edge $e=\{a,b\}\in E$ with $a\in A$ and $b\in B$ let $h(e)$ be the height of $e$ in $(\delta(b), \le_b)$. Choose a matching $M$ in $G$ with the property
$(\star)$ For every edge $e=\{a,b\}\in E$ with $a\in A$ and $b\in B$ it holds: If $f\le_a e$ for some $f\in M$, then $e\le_b g$ for some $g\in M$
and which maximizes $\sum_{e\in M} h(e)$ under all matchings with $(\star)$.
The claim is that now $M$ is stable, but I don't see why. The proof in the book is confusing, because too many things are called "$e$".
Edit: $\delta(v)$ is the set of all edges incident with $v$
I think what makes the statement and proof of the theorem less clear than it might be is the use of non-strict inequality. In condition $(18.23),\ e,f,\text{ and } g$ can all be the same edge. I think everything would be clearer if we had $e\notin M$ and strict inequality.
You may find the proof easier to follow if you cast it in terms of marriages as Gale and Shapley did. Let $U$ be the set of men and $W$ the set of women. Each person $v$ rates his potential mates form $1$ worst to $\delta(v)$ (best). Condition $(18.23)$ in the text means if any man $u$ would prefer to be married to some woman $w$ instead of his present wife, then $w$ is already married to a man she prefers to $u$.
The condition $\sum_{e\in M}{\phi(E)}$ is maximized means that the total satisfaction of the women is as large as possible, subject to condition $(18.23).$
Now for the proof. If we assume that some set of marriages $M$ satisfying condition $(18.23)$ and maximizing the satisfaction of the women is not stable, then there is a man $u$ and a woman $w$ who would like to marry; they are not married to each other now, and neither is in a relationship he or she prefers to the potential marriage. We can assume that $w$ is $u'$s first choice among all women who would accept him.
By condition $(18.23),\ u$ is not married. Now let $u$ and $w$ marry, ($w$ leaving her present husband if she was married). Obviously, this increases the total satisfaction of the women, since only $w's$ changes. Furthermore, the new set of marriages satisfies condition $(18.23),$ contradicting the definition of $M.$
I'll leave you to verify the last statement, noting simply that there are only three people whose situation has changed: $u, w,$ and $w's$ former husband, if any.
If everyone were married, condition $(18.23)$ would say that the marriages were stable, but there may be unmarried people even at the end, if the numbers of men and women are different. If I remember correctly, in the original paper, Gale and Shapley had the number of men and women equal, and the algorithm terminated when everyone was married. The statement in the book is a slight generalization.