How to prove that adding incoming edges to source node doesn't alter the max flow I am given a homework assignment on this question:


  Show that if we add any number of incoming arcs, with any capacities, to the source node, the maximum flow value remains unchanged. Similarly, show that if we add any number of outgoing arcs, with any capacities, at the sink node, the maximum flow value remains unchanged.


While, it can be graphically proved with the help of an example, I am unsure of how to prove it systematically (like usual proofs in textbooks)
Let $G=(V,E)$ be your input graph. Now consider a maximum flow $f$ on $G$. 


  Let $f$ be a flow in $G$ such that the residual network $G_R$ has no s-t path, then $f$ is a maximum flow.


Let's define $G'=(V,E')$ to be your graph  with $E'=E \cup \{(u_i,s)\}$  for $i=1,...,N$.   

Since $f$ is a maximum flow on $G$, then $G_R$ has no s-t paths.
Now you can show that given $G'$, its residual network $G'_R$ does not have any s-t path too. Thus, $f$ is a max flow also for $G'$.