We are supposed to find the maximum flow through this network $G$. We have that $val(f) \leq c(C)$ for every cut in the network, where $c(C)$ is the capacity of the cut $C$. So I understand I am supposed to find minimum cut. What confuses me is the definition that we have for cuts: a cut $C$ is each subset of $E(G)$ (edges in $G$), so that every path from $q$ (source) to $s$ (sink) contains at least one edge of $C$.
And I'm not supposed to use any specific algorithm, just the facts, that I have listed here. Thats what makes it diffcult for me since all definitons of a cut on the internet are different from this one and therefore also the approach to the problem
Aravind's definition of a cut is much more intuitive. Let's label your vertices from left to right, top to bottom starting from $1$. Note that $q = 5$ and $s = 8$. So for example, the vertex in the first row, second column is $2$. By inspection, if we choose $S = \{1, 2, 3, 5, 6, 7, 9, 10\}$, then the capacity of the cut is $5$. Let us call this cut $C^*$.
To see why $C^*$ is the minimum cut, note that the only edges with capacity less than $5$ are the edges $(3,4)$ and $(7, 11)$ (which we've used thus far in our solution) and $(6, q)$ and $(s, 7)$, both of which cannot cross a $q - s$ cut, since any edge to $q$ or from $s$ cannot cross a $q - s$ cut. (Why?) So the only possible candidates for a cut of smaller capacity would be cuts having only one of $(3, 4)$ or $(7, 11)$ flowing out of the $q$ side of the cut. To have a cut having only one of these edges flowing out of the $q$ side, we would have to move one of $4$ or $11$ to the $q$ side of $C^*$ or move one of $3$ or $4$ to the $s$ side of $C^*$. A quick check shows that none of these options reduces the minimum cut.