Sparse cuts, matching-cuts and leafy trees in graphs
Paul Bonsma · 2006
The graph shown on the cover of this thesis is one of the graphs used in the N P-completeness proofs of Chapter 3. The bold edges indicate a matching-cut in this graph, consisting of two of the six minimal matching-cuts possible in this graph. The cut consisting of the eleven dashed edges separates the graph into two parts with 56 vertices. This is a sparsest cut of the graph with density 0.0035. The 69 open vertices form the leaf set of a spanning tree of this graph. We do not know whether this number of leaves is maximum. Readers with plenty of spare time, that want to get an impression of the hardness of this problem, are invited to prove or disprove this.