 Solution

Given any admissible transport map $T$, form its graph transport planFor Borel sets $A\subseteq X$ and $B\subseteq Y$, the definition of a pushforward measure givesHence ${\pi }_T\in \Pi (\mu ,\nu )$. Integration against a pushforward measure also givesThe Kantorovich optimal transport problem therefore has at least all the competitors of the Monge optimal transport problem, with exactly the same costs. ConsequentlyIf there is no admissible transport map, the left side is $+\infty$ by the convention $\inf \varnothing =+\infty$, so the conclusion still holds. No existence of an optimizer is needed.