Max-Cut Instance:An undirected graph G(V,E). Solution:A bipartition of V into S and I that maximizes the cut E(S,T)={u,v}∈E|u∈S∧v∈T. max Yuv uw∈E s.t. yuv≤yuw+ywv, ,v,w∈V yuw+yuw+yu≤2，u,v,2w∈V yuw∈{0,1}， u,v∈V u,y,w∈V:0or2of{u,y以，{y,w以，{u,w} are“crossing pairs''Max-Cut Instance: An undirected graph . Solution: A bipartition of into and that maximizes the cut . G(V, E) V S T E(S, T) = {{u, v} ∈ E ∣ u ∈ S ∧ v ∈ T} T S max X uv2E yuv s.t. yuv 2 {0, 1}, yuv  yuw + ywv, yuv + yuw + ywv  2, 8u, v, w 2 V 8u, v, w 2 V 8u, v 2 V ∀u,v,w ∈ V: 0 or 2 of {u,v}, {v,w}, {u,w} are “crossing pairs