Problem #150: A minimal cut of a graph is a minimal set of vertices whose...

---

Progress

Asked by Erdős and Nešetřil, who also ask whether $c(3m+2)=3^m$. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

Solved by Bradač [Br24], who proved that $\alpha=\lim c(n)^{1/n}$ exists and\[\alpha \leq 2^{H(1/3)}=1.8899\cdots,\]where $H(\cdot)$ is the binary entropy function. Seymour's construction proves that $\alpha\geq 3^{1/3}=1.442\cdots$. Bradač conjectures that this lower bound is the true value of $\alpha$.