In this chapter we compare three popular models for the maximum cut problem and show the equivalence of their relaxations by using compact extended formulations. These problems are closely related to the subject of edge-induced and node-induced bipartite subgraphs, for which we give compact extended formulations as well.
