Initialize graph with all vertices and edges. Min_cut = infinity While : Run maximum adjacency ordering on to get vertex sequence. Let = second-to-last vertex, = last vertex. Cut_value = sum of edge weights from to all other vertices. Min_cut = min(min_cut, cut_value).
Merge and in (combine their edges into a supernode). Output min_cut. Each iteration considers one cut and contracts the graph.