[proofplan] We prove the submodularity inequality by decomposing the cut function into the contribution of each individual edge. For a fixed edge, its contribution depends only on which of the four regions $A\setminus B$, $B\setminus A$, $A\cap B$, and $V\setminus(A\cup B)$ contain its two endpoints. A complete case analysis shows that the edge contribution to $\delta(A)+\delta(B)$ is always at least its contribution to $\delta(A\cup B)+\delta(A\cap B)$. Multiplying by the non-negative capacity of the edge and summing over all edges gives the desired inequality. [/proofplan]

[step:Decompose the cut capacity into single-edge contributions] Fix arbitrary subsets $A,B\subset V$. For each edge $e=\{u,v\}\in E$, define the single-edge cut indicator $\kappa_e:2^V\to \{0,1\}$ by \begin{align*} \kappa_e(S):=\mathbb{1}_{\{|e\cap S|=1\}}. \end{align*} Thus $\kappa_e(S)=1$ exactly when the edge $e$ has one endpoint in $S$ and one endpoint in $V\setminus S$. By the definition of $\delta$, \begin{align*} \delta(S)=\sum_{e\in E} c(e)\kappa_e(S) \end{align*} for every $S\subset V$. Therefore it is enough to prove, for each fixed edge $e\in E$, that \begin{align*} \kappa_e(A)+\kappa_e(B)\geq \kappa_e(A\cup B)+\kappa_e(A\cap B), \end{align*} because multiplying this inequality by $c(e)\geq 0$ preserves the inequality and summing over the finite set $E$ preserves the inequality. [/step]

[step:Check the single-edge inequality by the four-region partition]Fix an edge $e=\{u,v\}\in E$. Define the four disjoint subsets $P:=A\setminus B$, $Q:=B\setminus A$, $R:=A\cap B$, and $T:=V\setminus(A\cup B)$. These four sets partition $V$. The value of $\kappa_e(A)$, $\kappa_e(B)$, $\kappa_e(A\cup B)$, and $\kappa_e(A\cap B)$ depends only on the two regions among $P,Q,R,T$ containing the endpoints $u$ and $v$. If both endpoints lie in the same one of $P,Q,R,T$, then neither endpoint is separated from the other by any of the sets $A$, $B$, $A\cup B$, or $A\cap B$, so all four indicators are $0$. It remains to consider the six unordered choices of two distinct regions for the endpoints of $e$. For endpoint regions $P$ and $Q$, the two sides are $2$ and $0$. For endpoint regions $P$ and $R$, the two sides are $1$ and $1$. For endpoint regions $P$ and $T$, the two sides are $1$ and $1$. For endpoint regions $Q$ and $R$, the two sides are $1$ and $1$. For endpoint regions $Q$ and $T$, the two sides are $1$ and $1$. For endpoint regions $R$ and $T$, the two sides are $2$ and $2$. In every case, the left-hand side is at least the right-hand side. Hence \begin{align*} \kappa_e(A)+\kappa_e(B)\geq \kappa_e(A\cup B)+\kappa_e(A\cap B) \end{align*} for this edge $e$.[/step]

[guided]We now prove the single-edge inequality in a way that isolates exactly where submodularity comes from. Fix an edge $e=\{u,v\}\in E$. Define $P:=A\setminus B$, $Q:=B\setminus A$, $R:=A\cap B$, and $T:=V\setminus(A\cup B)$. The sets $P,Q,R,T$ are pairwise disjoint and their union is $V$, so each endpoint of $e$ lies in exactly one of these four regions. The indicator $\kappa_e(S)$ records whether $S$ separates the two endpoints of $e$. Thus, to compute the four quantities \begin{align*} \kappa_e(A),\qquad \kappa_e(B),\qquad \kappa_e(A\cup B),\qquad \kappa_e(A\cap B), \end{align*} we only need to know the two regions containing $u$ and $v$. If both endpoints lie in the same region among $P,Q,R,T$, then no set built from membership in $A$ and $B$ separates them. In that case \begin{align*} \kappa_e(A)=\kappa_e(B)=\kappa_e(A\cup B)=\kappa_e(A\cap B)=0, \end{align*} and the desired inequality holds with equality. Now suppose the endpoints lie in two distinct regions. Since the edge is unordered, there are six cases. We compute each one. If the endpoint regions are $P$ and $Q$, then one endpoint lies in $A\setminus B$ and the other lies in $B\setminus A$. The set $A$ separates them, and the set $B$ also separates them. However, both endpoints lie in $A\cup B$, and neither endpoint lies in $A\cap B$. Hence \begin{align*} \kappa_e(A)+\kappa_e(B)=2, \qquad \kappa_e(A\cup B)+\kappa_e(A\cap B)=0. \end{align*} If the endpoint regions are $P$ and $R$, then both endpoints lie in $A$, but exactly one lies in $B$. Also both endpoints lie in $A\cup B$, while exactly one lies in $A\cap B$. Hence \begin{align*} \kappa_e(A)+\kappa_e(B)=0+1=1, \qquad \kappa_e(A\cup B)+\kappa_e(A\cap B)=0+1=1. \end{align*} If the endpoint regions are $P$ and $T$, then exactly one endpoint lies in $A$, no endpoint lies in $B$, exactly one endpoint lies in $A\cup B$, and no endpoint lies in $A\cap B$. Hence \begin{align*} \kappa_e(A)+\kappa_e(B)=1+0=1, \qquad \kappa_e(A\cup B)+\kappa_e(A\cap B)=1+0=1. \end{align*} If the endpoint regions are $Q$ and $R$, the same computation with $A$ and $B$ interchanged gives \begin{align*} \kappa_e(A)+\kappa_e(B)=1+0=1, \qquad \kappa_e(A\cup B)+\kappa_e(A\cap B)=0+1=1. \end{align*} If the endpoint regions are $Q$ and $T$, then $B$ separates the endpoints, $A$ does not separate them, $A\cup B$ separates them, and $A\cap B$ does not separate them. Therefore \begin{align*} \kappa_e(A)+\kappa_e(B)=0+1=1, \qquad \kappa_e(A\cup B)+\kappa_e(A\cap B)=1+0=1. \end{align*} Finally, if the endpoint regions are $R$ and $T$, then one endpoint lies in both $A$ and $B$, while the other lies in neither. Therefore both $A$ and $B$ separate the endpoints, and both $A\cup B$ and $A\cap B$ separate the endpoints: \begin{align*} \kappa_e(A)+\kappa_e(B)=1+1=2, \qquad \kappa_e(A\cup B)+\kappa_e(A\cap B)=1+1=2. \end{align*} Every possible placement of the two endpoints has now been covered. In each case, \begin{align*} \kappa_e(A)+\kappa_e(B)\geq \kappa_e(A\cup B)+\kappa_e(A\cap B). \end{align*}[/guided]

[step:Sum the single-edge inequalities with non-negative capacities] For every edge $e\in E$, the previous step gives \begin{align*} \kappa_e(A)+\kappa_e(B)\geq \kappa_e(A\cup B)+\kappa_e(A\cap B). \end{align*} Since $c(e)\geq 0$, multiplication by $c(e)$ gives \begin{align*} c(e)\kappa_e(A)+c(e)\kappa_e(B) \geq c(e)\kappa_e(A\cup B)+c(e)\kappa_e(A\cap B). \end{align*} Summing this inequality over the finite set $E$ yields \begin{align*} \sum_{e\in E}c(e)\kappa_e(A)+\sum_{e\in E}c(e)\kappa_e(B) \geq \sum_{e\in E}c(e)\kappa_e(A\cup B)+\sum_{e\in E}c(e)\kappa_e(A\cap B). \end{align*} Using the definition of $\delta$ on each sum, this becomes \begin{align*} \delta(A)+\delta(B)\geq \delta(A\cup B)+\delta(A\cap B). \end{align*} Because $A,B\subset V$ were arbitrary, $\delta$ is submodular. [/step]