Maximum cut

The problem can be stated simply as follows. One wants a subset S of the vertex set such that the number of edges between S and the complementary subset is as large as possible. Equivalently, one wants a bipartite subgraph of the graph with as many edges as possible. There is a more general version of the problem called weighted max-cut, where each edge is associated with a real number, its weight, and the objective is to maximize the total weight of the edges between S and its complement rather than the number of the edges. The weighted max-cut problem allowing both positive and negative weights can be trivially transformed into a weighted minimum cut problem by flipping the sign in all weights. Edwards obtained the following two lower bounds for maximum cuts on a graph G with n vertices and m edges: The bound for connected graphs is often called the Edwards–Erdős bound as Erdős conjectured it. Edwards proved the Edwards-Erdős bound using the probabilistic method; Crowston et al. proved the bound using linear algebra and analysis of pseudo-boolean functions.