It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special
pair of vertices, called a pendent pair, and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and
simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering
(MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different
type of special pair of vertices, called a flat pair, which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting
flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended
to the problem of finding extreme subsets in symmetric submodular set functions.
This is an extended abstract. This research was partially supported by the Scientific Grant-in-Aid from Ministry of Education,
Culture, Sports, Science and Technology of Japan.