 Solution

A transport plan is a Borel probability measure on $X\times Y$ with marginals $\mu ,\nu$. It is c-cyclically monotone when it is concentrated on a set $\Gamma$ such that every finite list $(x_i,y_i)\in \Gamma$ satisfiesEquivalently, one can allow every permutation of the destinations, since a permutation decomposes into cycles. The word $c$-monotone here means this cyclic condition, not merely a two-point test for an arbitrary cost.

The potential-certificate meaning of the printed “strictly $c$-monotone” is strong c-monotonicity: there are Borel functions $u:X\to \mathbb{R}\cup \{-\infty \}$ and $v:Y\to \mathbb{R}\cup \{-\infty \}$ such thatThe functions are finite on full marginal-measure sets. This is a certificate by Kantorovich potentials, not literal strict inequality in every nonidentity cycle. Such a literal interpretation could not satisfy the requested implication, already for $c=0$.

Here is a direct transport potential path construction. Since $c$ is finite and continuous, the closure of a cyclically monotone set remains cyclically monotone. We may therefore use the closed support $\Gamma$ of $\pi$ and choose a countable dense subset ${\Gamma }_0$, containing an anchor $(x_0,y_0)$. For a chain $(x_j,y_j)\in {\Gamma }_0$, $j=0,\dots ,m$, starting at that anchor, defineThe infimum is over countably many continuous functions, so $u$ is upper semicontinuous and Borel, and never $+\infty$ because the zero-length chain is available. Cyclical monotonicity applied to a chain closing at the anchor gives $u(x_0)=0$. If $(x,y)\in \Gamma$, closing a chain through this extra pair givesso $u(x)$ is finite on the first projection of $\Gamma$.

Append the pair $(x,y)$ to a nearly minimizing chain ending at $x$. If the pair is outside ${\Gamma }_0$, approximate it by pairs in ${\Gamma }_0$ and use continuity of the finitely many costs. This gives, for every $z$,Now putIt is again an infimum of continuous functions of $y$, and therefore upper semicontinuous and Borel. The anchor bounds it above by $c(x_0,y)$. Feasibility $u(z)+v(y)\le c(z,y)$ is immediate. For $(x,y)\in \Gamma$, the preceding chain inequality gives $v(y)\ge c(x,y)-u(x)$, while testing $z=x$ gives the opposite inequality. Hence equality holds on $\Gamma$, and $v$ is finite on its second projection. This proves cyclical monotonicity implies the potential certificate.

To deduce optimality, we must not subtract possibly infinite marginal integrals. Use the symmetric clipping proof of transport optimality: let $u_n=\max (-n,\min (u,n))$ and similarly $v_n$. Because $c\ge 0$, simultaneous clipping preserves the feasible inequalityFor any competitor ${\pi }^{\prime }$ with the same marginals, boundedness givesOn the full-measure equality set for $\pi$, $u+v=c\ge 0$. There the clipped sums are nonnegative and increase to $c$: when the two signs differ, their large equal clipping levels initially cancel, then the sum increases to the nonnegative original sum. Thus the monotone convergence theorem givesThis proves optimality even if the eventual integral is infinite. Conversely, a potential certificate implies the cyclic inequalities by summing and cancelling the potentials on its full-measure equality set.

The converse from optimality is true for finite-cost optimal plans. To see this, suppose points in the support violate a finite cyclic inequality by a positive amount. Continuity supplies product neighborhoods of those points on which every selected tuple still violates it, with all involved costs bounded. Normalize the restrictions of $\pi$ to these neighborhoods to probability measures ${\alpha }_i$, with marginals ${\mu }_i,{\nu }_i$. Subtract a sufficiently small common multiple of ${\sum }_i{\alpha }_i$ and add the same multiple of ${\sum }_i{\mu }_{i+1}\otimes {\nu }_i$. Positivity is ensured by choosing the multiple at most ${\min }_i\pi (U_i)/m$, even if neighborhoods overlap. Both marginals are unchanged, but integration of the strict cyclic improvement over the product of the ${\alpha }_i$ decreases the finite total cost. This contradicts optimality, so the support is cyclically monotone.

Without a finite-value hypothesis, the unrestricted converse is false. On the discrete Polish spaces $X=Y=\mathbb{N}$, take $\mu (n)=\nu (n)=C/n^2$ andThis is finite, continuous and nonnegative, yet every coupling has infinite cost because its marginals have infinite first moments. The diagonal plan is therefore an extended-value minimizer. Its support is not cyclically monotone: two distinct diagonal pairs cost $2m+2n+2$, while swapping their destinations costs $2m+2n$. Thus under the literal printed hypotheses, optimality alone need not imply $c$-monotonicity; the usual finite-cost converse needs that qualification.