# Show that no flow can have value exceeding $9$

Let $N$ be the network with source $u$ and sink $v$, where each are is label with its capacity.

a) Show that no flow can have value exceeding 9

b) Give an example of a flow $f$ on $N$ such that $val(f)=9$

My professor went through this very fast, so I don't think I can understand very well about flow. The number on the graph are the capacity of the arc, I know that the flow can't be bigger than the capacity, so for a), is it because the max capacity is from $x$ to $y$ and the biggest is $5+4=9$ so the flow of the whole network can't be bigger than 9? Why can't we have the max capacity be $5+3+2=10?$

For b) I know that $val(f)= f^+ -f^-= flowout - flow in$, but they only give me capacity, should I assume that the flow and capacity are the same?

• The two edges going into $v$ have a total capacity of $5+4=9$, so no more than $9$ can flow into $v$. For part (b), label each edge with a flow that is less than or equal to its capacity, so that every vertex but the source and sink has flowout=flowin. – vadim123 Nov 14 '14 at 18:28
• so the max flow is just the sum of in degree of the sink? – Diane Vanderwaif Nov 14 '14 at 18:30
• @Diane : Not always. It depends on the network. See : en.wikipedia.org/wiki/Max-flow_min-cut_theorem – Manuel Lafond Nov 14 '14 at 18:31
• @vadim123: Don’t you mean the minimum capacity of a set of edges that disconnects the graph? – Brian M. Scott Nov 14 '14 at 18:40
• @Diane: Looks good to me. – Brian M. Scott Nov 14 '14 at 19:18