A note on fragile graphs (Q1598838)

The authors prove the conjecture of Y. Caro that every graph on \(n\) vertices and at most \(2n-4\) edges contains an independent vertex-cut. The result is best possible, since the graph obtained from \(K_{2,n-2}\) by adding an edge between vertices of the part with just two vertices, has \(n\) vertices and \(2n-3\) edges, while none of its vertex-cuts is independent.