Phase Transition of Extremal Cuts