We prove the contrapositive. Suppose that \(H(M_1,M_2,Y)\) has a cycle of negative length and choose such a cycle \(C\) so that the number of vertices of \(C\) is minimized. Now, define
\begin{equation*}
S:= Y\triangle V(C).
\end{equation*}
By definition of the length function \(\ell\text{,}\) we have
\begin{equation*}
w(S) = w(Y\setminus V(C)) + w(V(C)\setminus Y)
\end{equation*}
\begin{equation*}
= w(Y\setminus V(C)) + w(Y\cap V(C)) + w(V(C)\setminus Y) -w(Y\cap V(C))
\end{equation*}
\begin{equation*}
= w(Y) - \ell(V(C)\setminus Y) -\ell(Y\cap V(C))
\end{equation*}
\begin{equation*}
= w(Y) - \ell(V(C)).
\end{equation*}
So, since \(C\) is a cycle of negative length, we have \(w(S)> w(Y)\text{.}\) Recall that every arc of \(H(M_1,M_2,Y)\) has exactly one endpoint in \(Y\) and one in \(X\setminus Y\text{.}\) Thus, \(|V(C)\cap Y| = |V(C)\setminus Y|\) and so \(|S|=|Y|\text{.}\) So, we must have \(S\notin\mathcal{I}_1\cap \mathcal{I}_2\) for, otherwise, it would contradict the assumption that \(Y\) is extremal. Since \(S\notin\mathcal{I}_1\cap \mathcal{I}_2\) can assume, without loss of generality, that \(S\notin\mathcal{I}_1\text{.}\) Our goal now is to find a shorter cycle of negative length which will contradict our choice of \(C\) and complete the proof.
Let
\(A_1\) be the set of arcs of
\(C\) that are directed from
\(Y\) to
\(X\setminus Y\) and
\(A_2\) be the set of arcs of
\(C\) directed from
\(X\setminus Y\) to
\(Y\text{.}\) The arcs in
\(A_1\) form a perfect matching from
\(Y\setminus S\) to
\(S\setminus Y\text{.}\) We claim that there exists another perfect matching
\(A_1'\neq A_1\) from
\(Y\setminus S\) to
\(S\setminus Y\) consisting of arcs that are directed from
\(Y\) to
\(X\setminus Y\text{.}\) Suppose not; i.e. suppose that
\(A_1\) is the unique such matching. We follow an argument similar to the proof of
Lemma 8.3.4. Let
\(Y\setminus S:=\{y_1,\dots,y_m\}\text{,}\) \(Y\cap S=\{y_{m+1},\dots,y_n\}\) and
\(S\setminus Y:= \{s_1,\dots,s_m\}\text{.}\) For each
\(0\leq i\leq m\text{,}\) define
\begin{equation*}
Y_i:=\{y_1,\dots,y_{m-i}\}\cup\{s_{m+1-i},\dots,s_m\}\cup\{y_{m+1},\dots,y_n\}.
\end{equation*}
We claim that
\(Y_i\in\mathcal{I}_1\) for all
\(0\leq i\leq m\text{,}\) which will suffice because
\(S=Y_m\) and by symmetry of
\(\mathcal{I}_1\) and
\(\mathcal{I}_2\text{.}\) The argument is very similar to the proof of
Lemma 8.3.4; see
Exercise 31.
Thus, there is a perfect matching \(A_1'\neq A_1\) from \(Y\setminus S\) to \(S\setminus Y\) consisting of arcs that are directed from \(Y\) to \(X\setminus Y\text{.}\) Let \(D\) be the multidigraph with vertex set \(V(C)\) whose arcs consist of \(A_1\text{,}\) \(A_1'\) and two copies of each arc in \(A_2\text{;}\) note that some arcs appear twice in \(D\text{.}\) Then every vertex of \(D\) has in-degree and out-degree equal to two. The digraph \(D\) contains all arcs of the cycle \(C\) and at least one arc from \(A_1'\setminus A_1\) that is not in \(C\text{.}\) By using an arc of \(A_1'\setminus A_1\) as a “shortcut” we can get a cycle \(C_1\) in \(D\) of shorter length than \(C\text{.}\) After removing the edges of \(C_1\text{,}\) we get a digraph in which every vertex has in-degree equal to their out-degree (which is either 1 or 2). So, we can find another cycle \(C_2\) in this digraph. Continue in this way until we have decomposed the edges of \(D\) into directed cycles \(C_1,\dots,C_k\text{.}\) By reordering the cycles if necessary, we can assume that \(|V(C_1)|\leq \cdots\leq |V(C_k)|\text{.}\) These cycles cover every vertex of \(V(C)\) exactly twice. So, since \(V(C_1)\neq V(C)\text{,}\) only one of these cycles can have vertex set equal to \(V(C)\text{;}\) by our choice of ordering, if such a cycle exists, then it is \(C_k\text{.}\) Using the fact that every vertex of \(V(C)\) is covered twice again, we have \(\sum_{j=1}^k\ell(C_j)=2\ell(C)\text{.}\) In the case that \(C_k=C\text{,}\) this implies that \(\sum_{j=1}^{k-1}\ell(C_j)=\ell(C)< 0\) and so at least one of the summands is negative. In the case that \(C_k\neq C\text{,}\) we have \(\sum_{j=1}^k\ell(C_j)=2\ell(C)< 0\) and, again, one of the summands is negative. In either case, we get a negative cycle of length shorter than \(C\) which contradicts our choice of \(C\) and completes the proof.
