An xcut of a set is defined to be a partition of V into two disjoint nonempty subsets such that both i and j are contained in the same subset. When partitions are associated with costs, the i-j xcut problem is defined to be the problem of computing an i-j xcut of minimum cost. This paper contains a proof that the minimum xcut problems have at most n distinct optimal solution values. These solutions can be compactly represented by a set of n partitions in such a way that the optimal solution to any of the problems can be found in time. For a special additive cost function that naturally arises in connection to graphs, some interesting properties of the set of optimal solutions that lead to a very simple algorithm are presented.
