Erdős Problem #150

A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let \(c(n)\) be the maximum number of minimal cuts a graph on \(n\) vertices can have. Does \(c(n)^{1/n}\to \alpha\) for some \(\alpha <2\)? It is unclear in [Er88] whether Erdős knew that the limit existed, which follows from a simple argument first given in the literature (to the best of my knowledge) by Bradač [Br24]. That \(\alpha<2\) was proved by Fomin, Kratsch, Todinca, and Villanger [FKTV08], who proved \(\alpha \leq 1.7087\). This was independently studied by Bradač [Br24] (unaware of this earlier work), who proved that \(\alpha \leq 2^{H(1/3)}\approx 1.8899\), where \(H(\cdot)\) is the binary entropy function. This was formalized in Lean by Monticone using Aristotle.