Random Cut for each vertex v∈V uniform independent Ye0,1} Y,=1 v∈S Y,=0> v∈T for each edge uv∈E Yu卡Yw IC(S,T)=>Yu )Yu=Yo uU∈D OPT EIC(S,T)川=>PY≠Y] 2 2 uw∈Efor each vertex v 2 V uniform & independent v 2 S v 2 T Yv 2 {0, 1} Yv = 1 Yv = 0 Yuv = ( 1 Yu 6= Yv 0 Yu = Yv for each edge uv 2 E |C(S, T)| = X uv2E Yuv E[|C(S, T)|] = X uv2E Pr[Yu 6= Yv] = |E| 2 ￾ OPT 2 Random Cut