There is a 'Maximum flow, minimum cut' theorem for which the proof is sketched in this question. Finding the solutions requires all cases to be checked.