Extremal Graphs Having No Stable Cutset

Abstract

A stable cutset in a graph is a stable set whose deletion disconnects the graph. It was conjectured by Caro and proved by Chen and Yu that any graph with $n$ vertices and at most $2n-4$ edges contains a stable cutset. The bound is tight, as we will show that all graphs with $n$ vertices and $2n-3$ edges without stable cutset arise recursively glueing together triangles and triangular prisms along an edge or triangle. As a by-product, an algorithmic implication of our result will be pointed out.