[proofplan]
We write the graph map as $S(x)=(x,T(x))$ and first verify that it is measurable for the product $\sigma$-algebra. The two marginal identities follow directly from the definition of pushforward measure by testing on measurable rectangles $A\times Y$ and $X\times B$. Finally, the integral identity is proved from the definition of the nonnegative integral: first for indicators, then for simple functions, and then by the standard monotone simple approximation of a nonnegative measurable function.
[/proofplan]
[step:Verify that the graph map is measurable]
Define
\begin{align*}
S:(X,\mathcal A)\to(X\times Y,\mathcal A\otimes\mathcal B),\quad S(x)=(x,T(x)).
\end{align*}
To prove that $S$ is measurable, it suffices to check preimages of measurable rectangles, since $\mathcal A\otimes\mathcal B$ is generated by sets of the form $A\times B$ with $A\in\mathcal A$ and $B\in\mathcal B$. For such $A$ and $B$,
\begin{align*}
S^{-1}(A\times B)=A\cap T^{-1}(B).
\end{align*}
Because $A\in\mathcal A$ and $T^{-1}(B)\in\mathcal A$ by measurability of $T$, the intersection $A\cap T^{-1}(B)$ belongs to $\mathcal A$. Hence $S$ is measurable, so the pushforward measure $\pi:=S_\#\mu$ is well-defined on $(X\times Y,\mathcal A\otimes\mathcal B)$.
Since $\mu$ is a probability measure,
\begin{align*}
\pi(X\times Y)=\mu(S^{-1}(X\times Y))=\mu(X)=1.
\end{align*}
Thus $\pi$ is a probability measure on $X\times Y$.
[/step]
[step:Compute the first marginal of the induced measure]
Let $p_X:X\times Y\to X$ denote the first coordinate projection, defined by $p_X(x,y)=x$. The first marginal of $\pi$ is $(p_X)_\#\pi$. Let $A\in\mathcal A$. Since $p_X^{-1}(A)=A\times Y$, the definition of pushforward gives
\begin{align*}
(p_X)_\#\pi(A)=\pi(A\times Y).
\end{align*}
Using $\pi=S_\#\mu$,
\begin{align*}
\pi(A\times Y)=\mu(S^{-1}(A\times Y)).
\end{align*}
For every $x\in X$, one has $S(x)=(x,T(x))\in A\times Y$ if and only if $x\in A$. Hence
\begin{align*}
S^{-1}(A\times Y)=A.
\end{align*}
Therefore
\begin{align*}
(p_X)_\#\pi(A)=\mu(A).
\end{align*}
Since this holds for every $A\in\mathcal A$, the first marginal of $\pi$ is $\mu$.
[/step]
[step:Compute the second marginal of the induced measure]
Let $p_Y:X\times Y\to Y$ denote the second coordinate projection, defined by $p_Y(x,y)=y$. The second marginal of $\pi$ is $(p_Y)_\#\pi$. Let $B\in\mathcal B$. Since $p_Y^{-1}(B)=X\times B$, the definition of pushforward gives
\begin{align*}
(p_Y)_\#\pi(B)=\pi(X\times B).
\end{align*}
Using $\pi=S_\#\mu$,
\begin{align*}
\pi(X\times B)=\mu(S^{-1}(X\times B)).
\end{align*}
For every $x\in X$, one has $S(x)=(x,T(x))\in X\times B$ if and only if $T(x)\in B$. Hence
\begin{align*}
S^{-1}(X\times B)=T^{-1}(B).
\end{align*}
Therefore
\begin{align*}
(p_Y)_\#\pi(B)=\mu(T^{-1}(B)).
\end{align*}
By the hypothesis $T_\#\mu=\nu$, the right-hand side equals $\nu(B)$. Thus
\begin{align*}
(p_Y)_\#\pi(B)=\nu(B).
\end{align*}
Since this holds for every $B\in\mathcal B$, the second marginal of $\pi$ is $\nu$.
The first marginal of $\pi$ is $\mu$ and the second marginal of $\pi$ is $\nu$, so by the definition of $\Pi(\mu,\nu)$ we have $\pi\in\Pi(\mu,\nu)$.
[/step]
[step:Prove the integral identity from the pushforward definition]
Let
\begin{align*}
c:X\times Y\to[0,\infty]
\end{align*}
be $\mathcal A\otimes\mathcal B$-measurable. Since $S$ is measurable, the composition
\begin{align*}
c\circ S:X\to[0,\infty],\quad (c\circ S)(x)=c(x,T(x)),
\end{align*}
is $\mathcal A$-measurable.
First let $E\in\mathcal A\otimes\mathcal B$ and consider the indicator function $\mathbb{1}_E:X\times Y\to[0,\infty]$. By the definition of pushforward measure,
\begin{align*}
\int_{X\times Y}\mathbb{1}_E(x,y)\,d\pi(x,y)=\pi(E)=\mu(S^{-1}(E)).
\end{align*}
Also,
\begin{align*}
\int_X \mathbb{1}_E(S(x))\,d\mu(x)=\int_X \mathbb{1}_{S^{-1}(E)}(x)\,d\mu(x)=\mu(S^{-1}(E)).
\end{align*}
Thus the identity holds for indicator functions.
By linearity of the integral for nonnegative simple functions, if
\begin{align*}
\varphi:X\times Y\to[0,\infty]
\end{align*}
is an $\mathcal A\otimes\mathcal B$-measurable [simple function](/page/Simple%20Function), then
\begin{align*}
\int_{X\times Y}\varphi(x,y)\,d\pi(x,y)=\int_X \varphi(S(x))\,d\mu(x).
\end{align*}
Choose a sequence of nonnegative $\mathcal A\otimes\mathcal B$-measurable simple functions
\begin{align*}
\varphi_n:X\times Y\to[0,\infty]
\end{align*}
such that $0\leq \varphi_n\leq \varphi_{n+1}$ for every $n\in\mathbb N$ and $\varphi_n(x,y)\to c(x,y)$ for every $(x,y)\in X\times Y$. Then $\varphi_n\circ S:X\to[0,\infty]$ is nonnegative, $\mathcal A$-measurable, increasing in $n$, and satisfies
\begin{align*}
\varphi_n(S(x))\to c(S(x))=c(x,T(x))
\end{align*}
for every $x\in X$. By the definition of the integral of a nonnegative measurable function as the limit of increasing simple approximations,
\begin{align*}
\int_{X\times Y} c(x,y)\,d\pi(x,y)=\lim_{n\to\infty}\int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y).
\end{align*}
For each $n$, the simple-function case gives
\begin{align*}
\int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y)=\int_X \varphi_n(S(x))\,d\mu(x).
\end{align*}
Taking the limit again by the definition of the nonnegative integral,
\begin{align*}
\lim_{n\to\infty}\int_X \varphi_n(S(x))\,d\mu(x)=\int_X c(S(x))\,d\mu(x).
\end{align*}
Since $c(S(x))=c(x,T(x))$, we obtain
\begin{align*}
\int_{X\times Y} c(x,y)\,d\pi(x,y)=\int_X c(x,T(x))\,d\mu(x).
\end{align*}
[guided]
The goal is to justify the formula for integrals without assuming it as a black-box change-of-variables theorem. The only input is the definition of $\pi$ as the pushforward $S_\#\mu$, where
\begin{align*}
S:(X,\mathcal A)\to(X\times Y,\mathcal A\otimes\mathcal B),\quad S(x)=(x,T(x)).
\end{align*}
Because $c:X\times Y\to[0,\infty]$ is $\mathcal A\otimes\mathcal B$-measurable and $S$ is measurable, the composition
\begin{align*}
c\circ S:X\to[0,\infty],\quad (c\circ S)(x)=c(x,T(x)),
\end{align*}
is $\mathcal A$-measurable, so the right-hand integral is well-defined.
We begin with an indicator function because the pushforward definition directly computes the measure of a preimage. Let $E\in\mathcal A\otimes\mathcal B$ and let $\mathbb{1}_E:X\times Y\to[0,\infty]$ be its indicator. Then
\begin{align*}
\int_{X\times Y}\mathbb{1}_E(x,y)\,d\pi(x,y)=\pi(E).
\end{align*}
Since $\pi=S_\#\mu$, the definition of pushforward gives
\begin{align*}
\pi(E)=\mu(S^{-1}(E)).
\end{align*}
On the other hand, the composed indicator satisfies
\begin{align*}
\mathbb{1}_E(S(x))=\mathbb{1}_{S^{-1}(E)}(x)
\end{align*}
for every $x\in X$. Hence
\begin{align*}
\int_X \mathbb{1}_E(S(x))\,d\mu(x)=\int_X\mathbb{1}_{S^{-1}(E)}(x)\,d\mu(x)=\mu(S^{-1}(E)).
\end{align*}
The two expressions are equal, so the integral identity holds for indicators.
Now pass from indicators to simple functions. Let
\begin{align*}
\varphi:X\times Y\to[0,\infty]
\end{align*}
be an $\mathcal A\otimes\mathcal B$-measurable simple function. It can be written as a finite nonnegative linear combination of indicators of measurable sets. Applying the indicator identity to each measurable set and using finite additivity and linearity of the nonnegative simple integral gives
\begin{align*}
\int_{X\times Y}\varphi(x,y)\,d\pi(x,y)=\int_X \varphi(S(x))\,d\mu(x).
\end{align*}
Finally let $c:X\times Y\to[0,\infty]$ be the given nonnegative measurable cost. Choose nonnegative $\mathcal A\otimes\mathcal B$-measurable simple functions
\begin{align*}
\varphi_n:X\times Y\to[0,\infty]
\end{align*}
with $0\leq\varphi_n\leq\varphi_{n+1}$ for every $n\in\mathbb N$ and $\varphi_n(x,y)\to c(x,y)$ for every $(x,y)\in X\times Y$. Composing with $S$ preserves the monotonicity and pointwise convergence:
\begin{align*}
\varphi_n(S(x))\to c(S(x))=c(x,T(x))
\end{align*}
for every $x\in X$. By the construction of the nonnegative measurable integral from increasing simple approximations,
\begin{align*}
\int_{X\times Y} c(x,y)\,d\pi(x,y)=\lim_{n\to\infty}\int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y).
\end{align*}
For each $n$, the simple-function identity gives
\begin{align*}
\int_{X\times Y}\varphi_n(x,y)\,d\pi(x,y)=\int_X \varphi_n(S(x))\,d\mu(x).
\end{align*}
Taking limits on the right-hand side using the same construction of the nonnegative integral gives
\begin{align*}
\lim_{n\to\infty}\int_X \varphi_n(S(x))\,d\mu(x)=\int_X c(S(x))\,d\mu(x).
\end{align*}
Substituting $S(x)=(x,T(x))$ yields
\begin{align*}
\int_{X\times Y} c(x,y)\,d\pi(x,y)=\int_X c(x,T(x))\,d\mu(x).
\end{align*}
[/guided]
[/step]
