algorithmnpnp-hard

Having trouble understanding the MAX-CUT problem

I'm having trouble understanding the general idea behind the MAX-CUT problem. Consider the graph below.

enter image description here

The MAX-CUT asks us to find the cut that maximizes the number of edges that it touches. I can trivially draw this.

enter image description here

I don't get what the problem is? For any graph, it's trivial for me to find the line that crosses all the edges. Am I misunderstanding the problem?

EDIT:

In response to David, here's a picture of my version of MAX-CUT where we end on an ending vertex

enter image description here

Solution

  • The formal definition of MAX-CUT is to find a set of vertices S to maximize the number of edges with exactly one endpoint in S. Graphically, this means drawing a simple closed curve and counting only the number of edges crossed an odd number of times.