Degree of cut equal to degree of source in digraph

Question

Let $D$ be a digraph and $s, t \in V (D)$. Suppose that $d_D^+(v)=d_D^-(v)$ for all $v \in V(D) \backslash \{s,t\} $. Let $S \subseteq V(D)$ with $s \in S$ and $t \in V (D) \backslash S $. Let $d_D^+(S)= |A_D^+(S) \cap A_D^-(V(D) \backslash S)| $be the number of arcs from $S$ to $V(D) \backslash S$, and $d_D^-(S)= |A_D^+(V(D)\backslash (S) \cap A_D^-(S)| $ the number of arcs from $V (D) \backslash S$ to $S$. How can I show that $d_D^+(s)-d_D^-(s)=d_D^+(S)-d_D^-(S)$. I undestand it intuitively (i.e. every vertex other than $s$ contributes nothing to the indegree and outdegree of $S$) but I think I'm missing an intermediate step or at least some rigor. I also thought to use the handshaking dilemma to show $d_D^+(s)-d_D^-(s)=-d_D^+(t)+d_D^-(t)$, but I don't see where to go from this. Maybe an inductive proof would work (start from two vertices and add one vertex to either $S$ or $T$ for the inductive step).

Answer 1

You should look at $$\sum_{v \in S} d^+(v) - \sum_{v \in S} d^-(v) = \sum_{v\in S} \left(d^+(v) - d^-(v)\right).$$ The right-hand side simplifies to $d^+(s) - d^-(s)$ without too much work.

The left-hand side should simplify to $d^+(S) - d^-(S)$, with the number of arcs within $S$ canceling between the two sums. That argument still may or may not feel rigorous to you; to take it to the next level of formality, write $$d^+(v) = \sum_{w : (v,w) \in A(D)} 1$$ (and similarly for $d^-(v)$) then interchange some sums.