2
$\begingroup$

Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$.

Prove or disprove: The value of a maximum flow for $N$ can’t be $56$.

I'm trying to figure out how to definitely prove this. I think that this is not possible because of no combination of $12X + 18Y$ (where $X$ and $Y$ are integers) will ever $= 56$. Is there a better way of saying this? Am I right to say that an integer solution to $12X + 18Y = 56$ is what the Fold-Fulkerson algorithm implies?

$\endgroup$
1
$\begingroup$

By the max flow min cut theorem, the maximum value of a flow equals the minimum capacity of a cut. The capacity of a cut is of the form 12x+18y, which can’t equal 56 because 56 is not a multiple of 6.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.