"Proof" that the minimum cut is the same as the smallest number of paths between elements.

mincut-smallest-paths-proof.txt

Say we have the graph G, and if we were to make the minimum cut,
we would have two subgraphs.

Say we have 2 nodes from G, then, we'll call them A and B.

There are two possibilities, then. Either A and B are in the same subgraph, or they aren't.

If they are in different subgraphs, then how many connections do they have to each other?
It must be the number that we cut, because that's the number of paths that connect the two
subgraphs. We know it can use each of these paths, because it can reach any other node in
its graph (that's what a graph is), and these cut paths connect the two graphs.
It can't have fewer than the number we cut, because that would imply we cut too many lines.
(if there's no path from A to B, then they are disjoint, and we have 2 subgraphs... no need
to cut any more edges)

Alternatively, A and B could be in the same subgraph. In this case, they must have more paths
to each other than to any element in the other subgraph. If this wasn't the case, then we
misidentified the subgraph, because cutting each of the paths between A and B would make them
disjoint, so they must be in separate graphs, and the number of cuts required was the number
of paths, which is fewer than our minimum cut.

So, the smallest number of paths between A and B, for all potential As and all potential Bs,
must be the minimum cut.