Min-UnCut

Min-UnCut is the problem of dividing the vertices of a finite undirected graph into two parts so as to minimize the number of edges within the parts. Either part may be empty, and the parts need not have equal size. Equivalently, it minimizes the number of edges whose deletion leaves a bipartite graph. For an unweighted graph with edges and at least two vertices, its optimum is , where is the maxcut size. A triangle graph has optimum 1, while a bipartite graph has optimum 0.