Logo
All Random Solved Random Open
OPEN
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. Is $c(3m+2)=3^m$? Does $c(n)^{1/n}\to \alpha$ for some $\alpha <2$?
Asked by Erdős and Nešetřil. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.