[proofplan]
The implication from subdifferentials to cyclic monotonicity is obtained by summing the subgradient inequalities around a finite cycle. For the converse, if $\Gamma$ is nonempty, we fix a base point and define a potential as the supremum of all affine path increments generated by finite chains in $\Gamma$. Cyclical monotonicity bounds these path increments at the base point and at every point of $\Gamma$, making the function proper and ensuring the required subgradient inequality.
[/proofplan]
[step:Sum the subgradient inequalities around a cycle]
Assume that there exists a proper convex function $\varphi: \mathbb{R}^n \to (-\infty,\infty]$ such that $y \in \partial \varphi(x)$ for every $(x,y) \in \Gamma$. Let $m \in \mathbb{N}$, let $(x_i,y_i) \in \Gamma$ for $i \in \{1,\dots,m\}$, and define $x_{m+1} := x_1$.
By the definition of the subdifferential, for each $i \in \{1,\dots,m\}$ and every $z \in \mathbb{R}^n$,
\begin{align*}
\varphi(z) \geq \varphi(x_i) + y_i \cdot (z - x_i).
\end{align*}
Taking $z := x_{i+1}$ gives
\begin{align*}
y_i \cdot (x_{i+1} - x_i) \leq \varphi(x_{i+1}) - \varphi(x_i).
\end{align*}
Summing over $i \in \{1,\dots,m\}$, the right-hand side telescopes:
\begin{align*}
\sum_{i=1}^{m} y_i \cdot (x_{i+1} - x_i) \leq \sum_{i=1}^{m} \bigl(\varphi(x_{i+1}) - \varphi(x_i)\bigr) = 0.
\end{align*}
Thus $\Gamma$ is cyclically monotone.
[guided]
Assume that $\Gamma$ is contained in the graph of the subdifferential of a proper convex function $\varphi: \mathbb{R}^n \to (-\infty,\infty]$. This means that whenever $(x_i,y_i) \in \Gamma$, the vector $y_i$ is a subgradient of $\varphi$ at $x_i$. By definition of the subdifferential, this gives the supporting affine inequality
\begin{align*}
\varphi(z) \geq \varphi(x_i) + y_i \cdot (z - x_i)
\end{align*}
for every $z \in \mathbb{R}^n$.
To prove cyclical monotonicity, choose an arbitrary finite cycle $(x_i,y_i) \in \Gamma$ for $i \in \{1,\dots,m\}$ and set $x_{m+1} := x_1$. The natural substitution is $z := x_{i+1}$, because cyclical monotonicity compares each vector $y_i$ with the displacement from $x_i$ to the next point in the cycle. The subgradient inequality becomes
\begin{align*}
\varphi(x_{i+1}) \geq \varphi(x_i) + y_i \cdot (x_{i+1} - x_i),
\end{align*}
or equivalently
\begin{align*}
y_i \cdot (x_{i+1} - x_i) \leq \varphi(x_{i+1}) - \varphi(x_i).
\end{align*}
Now sum these inequalities over the whole cycle. The terms involving $\varphi$ cancel because $x_{m+1}=x_1$:
\begin{align*}
\sum_{i=1}^{m} y_i \cdot (x_{i+1} - x_i) \leq \sum_{i=1}^{m} \bigl(\varphi(x_{i+1}) - \varphi(x_i)\bigr) = 0.
\end{align*}
This is exactly the defining finite-cycle inequality for cyclical monotonicity.
[/guided]
[/step]
[step:Handle the empty set case]
Assume now that $\Gamma$ is cyclically monotone. If $\Gamma = \varnothing$, define
\begin{align*}
\varphi: \mathbb{R}^n &\to (-\infty,\infty]
\end{align*}
\begin{align*}
z &\mapsto 0.
\end{align*}
Then $\varphi$ is proper and convex, and the containment condition is vacuous. Hence suppose for the rest of the proof that $\Gamma \neq \varnothing$.
[/step]
[step:Construct the Rockafellar potential from finite chains]
Choose a base point $(x_0,y_0) \in \Gamma$. For every $z \in \mathbb{R}^n$, define $\varphi(z)$ by
\begin{align*}
\varphi(z) := \sup \left\{ \sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (z - x_m) : m \in \mathbb{N}_0,\ (x_i,y_i) \in \Gamma \text{ for } i \in \{0,\dots,m\},\ (x_0,y_0) \text{ fixed} \right\}.
\end{align*}
Here $\mathbb{N}_0 := \mathbb{N} \cup \{0\}$, and when $m=0$ the empty sum is interpreted as $0$, so the corresponding affine function is $z \mapsto y_0 \cdot (z-x_0)$.
[/step]
[step:Use cyclic monotonicity to prove the potential is proper]
For each admissible finite chain $(x_i,y_i) \in \Gamma$ for $i \in \{0,\dots,m\}$, cyclic monotonicity applied to the cycle $x_0,x_1,\dots,x_m,x_0$ gives
\begin{align*}
\sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (x_0 - x_m) \leq 0.
\end{align*}
Therefore every affine expression in the defining supremum satisfies, at $z=x_0$,
\begin{align*}
\sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (x_0 - x_m) \leq 0.
\end{align*}
The chain with $m=0$ gives the value $0$ at $x_0$, so
\begin{align*}
\varphi(x_0)=0.
\end{align*}
Thus $\varphi$ is not identically $+\infty$ and has a nonempty effective domain. Since it is a supremum of real-valued affine functions, it never takes the value $-\infty$. Hence $\varphi$ is proper.
[/step]
[step:Observe that the potential is convex]
For each admissible chain, the map
\begin{align*}
A_{(x_i,y_i)_{i=0}^{m}}: \mathbb{R}^n &\to \mathbb{R}
\end{align*}
\begin{align*}
z &\mapsto \sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (z - x_m)
\end{align*}
is affine, hence convex. Since $\varphi$ is the pointwise supremum of the family of affine maps $A_{(x_i,y_i)_{i=0}^{m}}$, the function $\varphi: \mathbb{R}^n \to (-\infty,\infty]$ is convex.
[/step]
[step:Append one more edge to obtain the subgradient inequality]
Fix $(x,y) \in \Gamma$. First, $\varphi(x)$ is finite. Indeed, for any admissible chain $(x_i,y_i) \in \Gamma$ for $i \in \{0,\dots,m\}$, cyclic monotonicity applied to the cycle $x_0,x_1,\dots,x_m,x,x_0$, using the final pair $(x,y)$ at the point $x$, gives
\begin{align*}
\sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (x - x_m) + y \cdot (x_0 - x) \leq 0.
\end{align*}
Hence every affine expression defining $\varphi(x)$ is at most $y \cdot (x-x_0)$, so
\begin{align*}
\varphi(x) \leq y \cdot (x-x_0) < \infty.
\end{align*}
Also $\varphi(x) > -\infty$ because the chain with $m=0$ gives the finite lower bound $y_0 \cdot (x-x_0)$.
Now let $z \in \mathbb{R}^n$. By the definition of $\varphi(x)$ as a supremum, for every real number $a < \varphi(x)$ there exists an admissible chain $(x_i,y_i) \in \Gamma$ for $i \in \{0,\dots,m\}$ such that
\begin{align*}
a < \sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (x - x_m).
\end{align*}
Append the point $(x,y)$ to this chain. The defining supremum for $\varphi(z)$ then gives
\begin{align*}
\varphi(z) \geq \sum_{i=0}^{m-1} y_i \cdot (x_{i+1} - x_i) + y_m \cdot (x - x_m) + y \cdot (z-x).
\end{align*}
Therefore
\begin{align*}
\varphi(z) > a + y \cdot (z-x).
\end{align*}
Letting $a \uparrow \varphi(x)$ yields
\begin{align*}
\varphi(z) \geq \varphi(x) + y \cdot (z-x).
\end{align*}
Since this holds for every $z \in \mathbb{R}^n$, the definition of the subdifferential gives $y \in \partial \varphi(x)$. Because $(x,y) \in \Gamma$ was arbitrary,
\begin{align*}
\Gamma \subset \{(x,y) \in \mathbb{R}^n \times \mathbb{R}^n : y \in \partial \varphi(x)\}.
\end{align*}
This proves the converse implication and completes the proof.
[/step]
