[proofplan]
We prove submodularity by decomposing the outgoing cut capacity into a non-negative linear combination of single-arc cut indicators. For one fixed arc $e = (u,v)$, we verify the submodular inequality directly by comparing whether the tail $u$ and the head $v$ lie in the relevant subsets. Since submodular inequalities are preserved under sums with non-negative coefficients, summing the single-arc inequalities over all arcs gives the desired inequality for $\delta^+$.
[/proofplan]
[step:Represent the outgoing cut capacity as a weighted sum of single-arc indicators]
Let $c:E \to [0,\infty)$ denote the arc-capacity function. For each arc $e = (u,v) \in E$, define the single-arc outgoing cut indicator $\iota_e: 2^V \to \{0,1\}$ by declaring, for each subset $S \subset V$, that $\iota_e(S)=1$ when $u \in S$ and $v \notin S$, and that $\iota_e(S)=0$ otherwise. By the definition of $\delta^+$, for every subset $S \subset V$,
\begin{align*}
\delta^+(S) = \sum_{e \in E} c(e)\,\iota_e(S).
\end{align*}
Thus it is enough to prove that each function $\iota_e$ is submodular, because every coefficient $c(e)$ is non-negative.
[/step]
[step:Prove the submodular inequality for one directed arc]
Fix an arc $e = (u,v) \in E$. For any mathematical assertion $P$, let $\mathbb{1}_P \in \{0,1\}$ denote the indicator of $P$, equal to $1$ if $P$ is true and equal to $0$ if $P$ is false. We prove that for all $X,Y \subset V$,
\begin{align*}
\iota_e(X) + \iota_e(Y) \geq \iota_e(X \cup Y) + \iota_e(X \cap Y).
\end{align*}
If $u \notin X \cup Y$, then $u \notin X$, $u \notin Y$, $u \notin X \cup Y$, and $u \notin X \cap Y$. Hence all four indicator values are $0$, and the inequality holds with equality.
Assume next that $u \in X \cap Y$. Then
\begin{align*}
\iota_e(X) + \iota_e(Y)
=
\mathbb{1}_{\{v \notin X\}} + \mathbb{1}_{\{v \notin Y\}},
\end{align*}
while
\begin{align*}
\iota_e(X \cup Y) + \iota_e(X \cap Y)
=
\mathbb{1}_{\{v \notin X \cup Y\}} + \mathbb{1}_{\{v \notin X \cap Y\}}.
\end{align*}
If $v \notin X \cup Y$, both sides are $2$. If $v \in X \cap Y$, both sides are $0$. If $v$ lies in exactly one of $X$ and $Y$, both sides are $1$. Therefore the inequality holds in this case.
It remains to consider the case where $u$ lies in exactly one of $X$ and $Y$. By symmetry between $X$ and $Y$, assume $u \in X \setminus Y$. Then $\iota_e(Y)=0$ and $\iota_e(X \cap Y)=0$, since $u \notin Y$ and $u \notin X \cap Y$. Also $u \in X \cup Y$. Hence $\iota_e(X \cup Y)=1$ if $v \notin X \cup Y$, and $\iota_e(X \cup Y)=0$ if $v \in X \cup Y$. If $v \notin X \cup Y$, then $v \notin X$, so $\iota_e(X)=1=\iota_e(X \cup Y)$. If $v \in X \cup Y$, then $\iota_e(X \cup Y)=0$, and the inequality follows from $\iota_e(X)\geq 0$. Hence the single-arc inequality holds in all cases.
[guided]
Fix an arc $e = (u,v) \in E$. For any mathematical assertion $P$, let $\mathbb{1}_P \in \{0,1\}$ denote the indicator of $P$, equal to $1$ if $P$ is true and equal to $0$ if $P$ is false. The function $\iota_e$ records exactly one event: the tail $u$ is inside the set and the head $v$ is outside the set. We must prove that for arbitrary subsets $X,Y \subset V$,
\begin{align*}
\iota_e(X) + \iota_e(Y) \geq \iota_e(X \cup Y) + \iota_e(X \cap Y).
\end{align*}
The only relevant information is the membership of $u$ and $v$ in $X$ and $Y$. We separate the proof according to where the tail $u$ lies.
First suppose $u \notin X \cup Y$. Then $u$ is in none of $X$, $Y$, $X \cup Y$, or $X \cap Y$. Since $\iota_e(S)$ can equal $1$ only when $u \in S$, all four values are $0$:
\begin{align*}
\iota_e(X) = \iota_e(Y) = \iota_e(X \cup Y) = \iota_e(X \cap Y) = 0.
\end{align*}
Thus the desired inequality holds with equality.
Now suppose $u \in X \cap Y$. Then $u$ belongs to all four sets $X$, $Y$, $X \cup Y$, and $X \cap Y$. Therefore each indicator is controlled only by whether $v$ is outside the relevant set:
\begin{align*}
\iota_e(X) + \iota_e(Y)
=
\mathbb{1}_{\{v \notin X\}} + \mathbb{1}_{\{v \notin Y\}},
\end{align*}
and
\begin{align*}
\iota_e(X \cup Y) + \iota_e(X \cap Y)
=
\mathbb{1}_{\{v \notin X \cup Y\}} + \mathbb{1}_{\{v \notin X \cap Y\}}.
\end{align*}
There are three possibilities for $v$. If $v \notin X \cup Y$, then $v$ is outside both $X$ and $Y$, so both sides are $2$. If $v \in X \cap Y$, then $v$ is inside both $X$ and $Y$, so both sides are $0$. If $v$ lies in exactly one of $X$ and $Y$, then exactly one of $\mathbb{1}_{\{v \notin X\}}$ and $\mathbb{1}_{\{v \notin Y\}}$ equals $1$, while $v \in X \cup Y$ and $v \notin X \cap Y$, so the right-hand side is also $1$. Hence the inequality holds whenever $u \in X \cap Y$.
Finally suppose $u$ lies in exactly one of $X$ and $Y$. Interchanging the names of $X$ and $Y$ does not change the desired inequality, so it suffices to treat the case $u \in X \setminus Y$. Then $u \notin Y$ and $u \notin X \cap Y$, which forces $\iota_e(Y)=0$ and $\iota_e(X \cap Y)=0$. Also $u \in X \cup Y$. If $v \notin X \cup Y$, then in particular $v \notin X$, so
\begin{align*}
\iota_e(X)=1
\qquad\text{and}\qquad
\iota_e(X \cup Y)=1.
\end{align*}
The desired inequality is then an equality. If instead $v \in X \cup Y$, then $\iota_e(X \cup Y)=0$, and the right-hand side is $0$ because $\iota_e(X \cap Y)=0$. Since indicators are non-negative, the left-hand side is at least $0$. Thus the inequality holds in this remaining case as well.
These cases exhaust all possible positions of the tail $u$ relative to $X$ and $Y$, so $\iota_e$ is submodular.
[/guided]
[/step]
[step:Sum the single-arc inequalities with the non-negative capacities]
For every arc $e \in E$, the preceding step gives
\begin{align*}
\iota_e(X) + \iota_e(Y) \geq \iota_e(X \cup Y) + \iota_e(X \cap Y).
\end{align*}
Multiplying this inequality by $c(e) \geq 0$ preserves the inequality:
\begin{align*}
c(e)\,\iota_e(X) + c(e)\,\iota_e(Y)
\geq
c(e)\,\iota_e(X \cup Y) + c(e)\,\iota_e(X \cap Y).
\end{align*}
Summing over the finite arc set $E$ gives
\begin{align*}
\sum_{e \in E} c(e)\,\iota_e(X) + \sum_{e \in E} c(e)\,\iota_e(Y) \geq \sum_{e \in E} c(e)\,\iota_e(X \cup Y) + \sum_{e \in E} c(e)\,\iota_e(X \cap Y).
\end{align*}
Using the representation of $\delta^+$ from the first step, this becomes
\begin{align*}
\delta^+(X) + \delta^+(Y) \geq \delta^+(X \cup Y) + \delta^+(X \cap Y).
\end{align*}
Since $X,Y \subset V$ were arbitrary, $\delta^+$ is submodular.
[/step]
