On a question of Erdős and Nešetřil about minimal cuts in a graph

Abstract

Answering a question of Erdős and Nešetřil, we show that the maximum number of inclusion-wise minimal vertex cuts in a graph on $n$ vertices is at most $1.8899^n$ for large enough $n$.

The results were already known prior to this work. The bounds proved here are superseded by earlier results of Fomin-Kratsch-Todinca-Villanger, Fomin-Villanger and Gaspers-Mackenzie; see the note and references added in this version