Jaehyeon

Heo

(Teddy)

part (a)

If the original flow sends f(u,v)=c, keep every other edge the same and route that exact amount through the new vertex by setting f(u,x)=f(x,v)=c. Any feasible flow in G maps to a feasible one in G' with the same value, and vice versa, so the maximum-flow value is unchanged.

part (b)

Replace every vertex $v\neq s, t$ by two nodes $v_{in}$ and $v_{out}$, add a single bridge edge $(v_{in},v_{out})$ with capacity $\ell(v)$, send all original incoming edges into $v_{in}$, and all original outgoing edges out of $v_{out}$ (keeping their original capacities). This enforces the vertex limit without explicitly storing it. If the original graph has $n$ vertices and $m$ edges, $G'$ ends up with $n + (n-2) = 2n-2$ vertices and $m + (n-2)$ edges.