Let $X$ and $Y$ be Polish spaces equipped with their Borel $\sigma$-algebras $\mathcal{B}(X)$ and $\mathcal{B}(Y)$. Let $\mu \in \mathcal{P}(X)$ and $\nu \in \mathcal{P}(Y)$, and let $\Pi(\mu,\nu)$ denote the set of Borel probability measures $\gamma$ on $X\times Y$ whose first marginal is $\mu$ and whose second marginal is $\nu$. Let $c: X \times Y \to [0,\infty]$ be a Borel measurable cost function, and define the cost functional $\mathcal{C}:\Pi(\mu,\nu)\to[0,\infty]$ by

\begin{align*} \mathcal{C}(\gamma):=\int_{X\times Y} c(z)\,d\gamma(z). \end{align*}

Assume that $\pi\in\Pi(\mu,\nu)$ is optimal for $c$, meaning that

\begin{align*} \mathcal{C}(\pi)\leq \mathcal{C}(\gamma) \end{align*}

for every $\gamma\in\Pi(\mu,\nu)$, and assume that $\mathcal{C}(\pi)<\infty$. For each $n\in\mathbb{N}$, let $\pi^{\otimes n}$ denote the $n$-fold product probability measure on $(X\times Y)^n$. Then there exists a Borel set $\Gamma \subset X \times Y$ such that $\pi(\Gamma)=1$ and $\Gamma$ is $c$-cyclically monotone: for every $n \in \mathbb{N}$, every finite family $(x_i,y_i)_{i=1}^n \subset \Gamma$, and every permutation $\sigma$ of $\{1,\dots,n\}$,

\begin{align*} \sum_{i=1}^n c(x_i,y_i) \leq \sum_{i=1}^n c(x_i,y_{\sigma(i)}). \end{align*}