Lesson 1

In the maximum flow problem, there is a source and a sink: some amount enters the network at one special vertex and leaves it at another. There is also a more symmetric way to think about flows. Imagine a closed system of pipes in which liquid only circulates. At every junction, exactly as much liquid enters as leaves. There is no source, no sink, and no capacity constraint.

This model looks less practical at first, but it leads to a beautiful counting question. How many ways are there to assign nonzero values to all edges so that the conservation law holds everywhere? The answer is controlled by a polynomial, much as the chromatic polynomial controls proper colorings.