A simple proof of a minimum cut algorithm and its applications

For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple p roofs have been presented so far. This paper gives yet another simple proof . As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorit hm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAG(s,t) that r epresents all minimum cuts separating vertices s and t in a graph G, and th e algorithm to compute the cactus Gamma(G) that represents all minimum cuts in G.