Question

Consider a flow network on 10 vertices (including the source and the sink), consisting of a single path starting at a source s and ending at a sink t. The capacities of all edges are qual to 1. How many cuts does this flow network have? How many of them are min-cuts?

Answer 1

The vertices are aligned in the same line because there exists only a single path between source and sink. In a flow network there are no stray vertices, every vertex must be contained in a path between source and sink.

Now since there are 10 vertices and it is a single path graph. Number of edges is 9.

Removing any of these edges provides us with two disjoint sets A, B with s-t cut capcity = capacity of that edge = 1

Hence all the 9 edges are cuts. Also they have equal cut capacities. And hence all these cuts are min-cuts also.