[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.[/step]

[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: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]