[proofplan] We first use the finite-cost hypothesis to restrict to a full-measure set on which the cost is finite, so all later strict cost comparisons avoid undefined expressions involving $\infty-\infty$. For each finite length $n$ and permutation $\sigma$, we form the Borel set of $n$-tuples that violate the corresponding cyclic inequality. The finite-cycle rerouting lemma says that any positive-measure violating family can be rerouted into a competitor with the same marginals and strictly smaller cost, contradicting optimality. Once all violating families are null, the measurable-envelope lemma for Polish spaces produces a Borel full-$\pi$-measure set on which every finite cyclic inequality holds. [/proofplan]

[step:Restrict to the finite-cost region]The set $\Pi(\mu,\nu)$ denotes the set of Borel probability measures on $X\times Y$ with first marginal $\mu$ and second marginal $\nu$. The cost functional $\mathcal{C}: \Pi(\mu,\nu) \to [0,\infty]$ is defined in the statement by \begin{align*} \mathcal{C}(\gamma) := \int_{X \times Y} c(z)\, d\gamma(z). \end{align*} The hypothesis gives $\mathcal{C}(\pi)<\infty$. Let \begin{align*} Z := \{(x,y) \in X \times Y : c(x,y)<\infty\}. \end{align*} Since $c$ is Borel measurable, $Z$ is Borel. If $\pi((X \times Y)\setminus Z)>0$, then the non-negative integral of $c$ with respect to $\pi$ is infinite. Hence $\pi(Z)=1$.[/step]

[guided]The cost $c$ is allowed to take the value $\infty$, so the first task is to remove the part of the transport plan where this happens. The notation $\Pi(\mu,\nu)$ means the set of Borel probability measures on $X\times Y$ with first marginal $\mu$ and second marginal $\nu$. The cost functional $\mathcal{C}: \Pi(\mu,\nu) \to [0,\infty]$ is defined in the statement by \begin{align*} \mathcal{C}(\gamma) := \int_{X \times Y} c(z)\, d\gamma(z). \end{align*} The theorem assumes $\mathcal{C}(\pi)<\infty$. Now define the finite-cost set \begin{align*} Z := \{(x,y) \in X \times Y : c(x,y)<\infty\}. \end{align*} Because $c: X \times Y \to [0,\infty]$ is Borel measurable, the set $Z=c^{-1}([0,\infty))$ is Borel. If $\pi((X \times Y)\setminus Z)>0$, then $c=\infty$ on a set of positive $\pi$-measure, and since $c$ is non-negative, \begin{align*} \int_{X \times Y} c(z)\, d\pi(z)=\infty. \end{align*} This contradicts the finite-cost hypothesis. Therefore $\pi(Z)=1$. This reduction matters because the cyclic inequalities compare finite sums of costs. On $Z$, every original pair $(x,y)$ used by the plan has finite cost, so strict inequalities of the form “old cost is larger than rerouted cost” are legitimate numerical inequalities.[/guided]

[step:Define the measurable finite-cycle violation sets] For $n \in \mathbb{N}$, let $\pi^{\otimes n}$ denote the $n$-fold product probability measure on $(X\times Y)^n$, as in the statement. For such $n$ and a permutation $\sigma$ of $\{1,\dots,n\}$, define the Borel maps $A_{n,\sigma},B_{n,\sigma}: (X \times Y)^n \to [0,\infty]$ by \begin{align*} A_{n,\sigma}((x_1,y_1),\dots,(x_n,y_n)) := \sum_{i=1}^n c(x_i,y_i) \end{align*} and \begin{align*} B_{n,\sigma}((x_1,y_1),\dots,(x_n,y_n)) := \sum_{i=1}^n c(x_i,y_{\sigma(i)}). \end{align*} Let \begin{align*} V_{n,\sigma} := \{((x_1,y_1),\dots,(x_n,y_n)) \in Z^n : A_{n,\sigma} > B_{n,\sigma}\}. \end{align*} Since $c$ is Borel and finite sums of Borel extended-real-valued functions are Borel, $A_{n,\sigma}$ and $B_{n,\sigma}$ are Borel. Hence $V_{n,\sigma}$ is Borel in $(X \times Y)^n$. [/step]

[step:Rule out positive-measure finite-cycle violations by optimality]We claim that \begin{align*} \pi^{\otimes n}(V_{n,\sigma})=0 \end{align*} for every $n \in \mathbb{N}$ and every permutation $\sigma$ of $\{1,\dots,n\}$. Suppose instead that $\pi^{\otimes n}(V_{n,\sigma})>0$ for some $n$ and $\sigma$. On $V_{n,\sigma}$, the old finite-cycle cost $A_{n,\sigma}$ is finite because $V_{n,\sigma}\subset Z^n$, and the strict inequality $A_{n,\sigma}>B_{n,\sigma}$ forces $B_{n,\sigma}<\infty$ there as well. By the finite-cycle rerouting part of the Rüschendorf-Kellerer monotonicity principle for Borel costs on Polish spaces, applied with the Polish probability space $(X\times Y,\mathcal{B}(X\times Y),\pi)$, the Borel set $V_{n,\sigma}\subset (X\times Y)^n$, and the fixed permutation $\sigma$, there exists a transport plan $\tilde{\pi}\in\Pi(\mu,\nu)$ obtained by a measurable finite-cycle exchange: a nonzero finite Borel measure dominated by $\pi$ is removed from the original pairings $(x_i,y_i)$, and the corresponding pushforward under the Borel rerouting map $((x_i,y_i))_{i=1}^n\mapsto((x_i,y_{\sigma(i)}))_{i=1}^n$ is inserted along the rerouted pairings $(x_i,y_{\sigma(i)})$. The hypotheses of the principle are satisfied because $X\times Y$ is Polish, $c$ is Borel, $V_{n,\sigma}$ is Borel, $\pi^{\otimes n}(V_{n,\sigma})>0$, the original cycle costs are finite on $V_{n,\sigma}\subset Z^n$, and $A_{n,\sigma}>B_{n,\sigma}$ on $V_{n,\sigma}$. This construction preserves both coordinate marginals and gives \begin{align*} \int_{X \times Y} c(z)\, d\tilde{\pi}(z) < \int_{X \times Y} c(z)\, d\pi(z). \end{align*} Here the preservation of the first marginal follows because the rerouting keeps the same list of source points $x_1,\dots,x_n$, and preservation of the second marginal follows because $\sigma$ only permutes the target points $y_1,\dots,y_n$. The strict decrease follows from the strict inequality $A_{n,\sigma}>B_{n,\sigma}$ on a selected positive-measure Borel subset of $V_{n,\sigma}$; the finite-cost reduction above makes the comparison finite on the removed and inserted pieces. This contradicts the optimality of $\pi$ among all plans in $\Pi(\mu,\nu)$. Therefore $\pi^{\otimes n}(V_{n,\sigma})=0$ for every $n$ and $\sigma$.[/step]

[guided]We prove that no finite-cycle violation can occur on a set of positive product measure. Fix $n \in \mathbb{N}$ and a permutation $\sigma$ of $\{1,\dots,n\}$. Assume for contradiction that \begin{align*} \pi^{\otimes n}(V_{n,\sigma})>0. \end{align*} A point of $V_{n,\sigma}$ is an $n$-tuple $((x_1,y_1),\dots,(x_n,y_n))$ of pairs already used by the plan, and it satisfies \begin{align*} \sum_{i=1}^n c(x_i,y_i) > \sum_{i=1}^n c(x_i,y_{\sigma(i)}). \end{align*} Because $V_{n,\sigma}\subset Z^n$, each original cost $c(x_i,y_i)$ is finite. Hence the left-hand side is finite, and the strict inequality implies the rerouted right-hand side is finite as well. Now apply the finite-cycle rerouting part of the Rüschendorf-Kellerer monotonicity principle for Borel costs on Polish spaces. This measurable selection and mass-splitting result says: if $(S,\mathcal{B}(S),\lambda)$ is a Polish probability space, $E\subset S^n$ is Borel with $\lambda^{\otimes n}(E)>0$, and a fixed permutation of the second coordinates strictly lowers the finite total cost on $E$, then there is a nonzero finite Borel measure dominated by the transport plan whose mass can be removed from the original pairings, while the pushforward under the associated Borel rerouting map inserts the same amount of mass along the rerouted pairings. Here $S=X\times Y$, $\lambda=\pi$, and $E=V_{n,\sigma}$. The hypotheses are satisfied because $X\times Y$ is Polish, $V_{n,\sigma}$ is Borel, $\pi^{\otimes n}(V_{n,\sigma})>0$, and the inequality $A_{n,\sigma}>B_{n,\sigma}$ holds with finite original cost on $V_{n,\sigma}\subset Z^n$. The resulting measure, call it $\tilde{\pi}$, is still a coupling of $\mu$ and $\nu$. The first marginal is unchanged because the source points in each finite cycle remain exactly $x_1,\dots,x_n$. The second marginal is unchanged because $\sigma$ merely permutes the target points $y_1,\dots,y_n$. Thus \begin{align*} \tilde{\pi}\in\Pi(\mu,\nu). \end{align*} The total cost strictly decreases because the inserted mass has smaller total $c$-cost than the removed mass on a positive-measure family of cycles: \begin{align*} \int_{X \times Y} c(z)\, d\tilde{\pi}(z) < \int_{X \times Y} c(z)\, d\pi(z). \end{align*} The finite-cost assumption is essential here: it ensures that this is a genuine comparison of finite costs on the pieces being exchanged, not an invalid subtraction of infinite quantities. But $\pi$ was assumed optimal among all couplings in $\Pi(\mu,\nu)$. Since $\tilde{\pi}\in\Pi(\mu,\nu)$ has strictly smaller cost, we get a contradiction. Hence \begin{align*} \pi^{\otimes n}(V_{n,\sigma})=0. \end{align*} Because $n$ and $\sigma$ were arbitrary, every measurable finite-cycle violation set is null.[/guided]

[step:Construct a Borel full-measure set satisfying all cyclic inequalities] Apply the measurable-envelope part of the Rüschendorf-Kellerer monotonicity principle to the Polish space $X\times Y$, the probability measure $\pi$, the full-measure Borel set $Z$, and the countable family of Borel null sets $(V_{n,\sigma})$, where $n\in\mathbb{N}$ and $\sigma$ ranges over the finite permutation group of $\{1,\dots,n\}$. The countability condition holds because the union is over countably many finite permutation groups, and the nullity condition holds by the preceding step: $\pi^{\otimes n}(V_{n,\sigma})=0$ for each pair $(n,\sigma)$. The principle yields a Borel set $\Gamma \subset Z \subset X \times Y$ such that $\pi(\Gamma)=1$ and, for every $n \in \mathbb{N}$, every permutation $\sigma$ of $\{1,\dots,n\}$, and every finite family $(x_i,y_i)_{i=1}^n \subset \Gamma$, \begin{align*} \sum_{i=1}^n c(x_i,y_i) \leq \sum_{i=1}^n c(x_i,y_{\sigma(i)}). \end{align*} Thus $\Gamma$ is $c$-cyclically monotone by definition. Since $\pi(\Gamma)=1$, the plan $\pi$ is concentrated on $\Gamma$. This proves the theorem. [/step]