Combinatorial and geometric properties of the max-cut and min-cut problems (Q393848)

Let \(G=(V,E)\) be an undirected graph with a function (weight) \(f\) from \(E\) into nonnegative integers. A pair \(\{P,Q\}\) of disjoint subsets of \(V\) is a cut and its value is the sum of weights of edges connecting \(P\) and \(Q\). The paper brings some facts about combinatorial and geometric properties of the min-cut problem (finding a cut with the minimal value) and of the max-cut problem (finding a cut with the maximal value). The difference between these problems is discussed.