Given the network flow R = (G,s,t,c), where the digraph G is G = (V,E) and the grid G - {s,t} has n x n vertices, north-south, west-east oriented and all the edges has the capacity 1, I need to prove that the maximum flow in R is n.
The maximum flow is the net flow leaving the source. We suppose that $ \forall v \in V - \{s,t\} $, it sends the flow to the neighbour to the right, such that it goes in a straight line to t ( like that ), then because we have n vertices on every "column", the flow reaching t will be n. In other cases if one of the vertices sends the flow north-south oriented, the vertice underneath it will receive 1 from the left neighbour and 1 from the upper neightbour, which will cause it to send 1 to the neighbour to the right and 1 to the underneath beighbour and so on until it reaches the vertice on the last line, where it will receive 2 units of flow, but will be able to send forward just 1, which makes this kind of configuration invalid. So we can deduce that the only valid configuration which determinates a maximum flow n is the initial one.
I don't know how to put this in mathematical notation, or even if my theory (put into mathematical notation) would be sufficient proof. So my questions are:
How should I go about formalizing this idea?
Is it sufficient to prove the initial requirement?
If not, then what should I add/look into?
Thanks in advance!
Hint: There can certainly be flows where flow passes through vertical edges. However, I think you are trying to argue that there is no max flow where flow passes through vertical edges. To argue that this is the case, show that for any flow $f$, if in $f$ some unit of flow passes through a vertical (downward) edge of the grid, then $v(f) < n$.
One possible approach is as follows: number the "rows" of the grid by $1, 2, \dots, n$. Then, given a flow $f$ in which flow travels downward somewhere, there exists a row $i$ such that flow travels from row $i$ to row $i + 1$, and that for all rows above $i$, no flow travels vertically. In other words, row $i$ is the uppermost row in which flow travels vertically. Then, think about whether it is possible for flow to travel from the right end of row $i$ to $t$. Then, note that if $v(f) = n$, $n$ units of flow reach $t$, and if $n$ units of flow reach $t$, then somehow a unit of flow must travel from the right end of row $i$ to $t$.
You, also need to show that no flow can have value greater than $n$, in order to prove that $n$ really is the maximum possible flow. (But this part isn't so difficult.)