Erdős Problem #150

Erdős Problem #150: an elementary exponential upper bound for minimal cuts

Partial reconstruction of the known resolution, 23 September 2026.

1) Statement and convention

Let $c(n)$ be the maximum number of inclusion-minimal vertex cuts in an $n$-vertex graph. The question asks whether $c(n)^{1/n}$ has a limit smaller than two. Here a cut leaves at least two nonempty connected components, and inclusion-minimality means that no proper subset is a cut. We prove \[ 3^{1/3}\le\liminf_{n\to\infty}c(n)^{1/n} \le\limsup_{n\to\infty}c(n)^{1/n} \le2^{H(1/3)}<2,\tag{1} \] where $H(x)=-x\log_2x-(1-x)\log_2(1-x)$. The remaining convergence step is not reconstructed in this file. The published resolution establishes existence of the limit and stronger upper bounds.

2) A cut is determined by a small set

Let $T$ be a minimal cut and $C$ any component of $G-T$. Its outer neighbourhood is exactly $T$. Certainly $N(C)\subseteq T$. If $x\in T$ had no neighbour in $C$, restoring $x$ would leave $C$ separated from every other component of $G-T$. Thus $T\setminus\{x\}$ would still be a cut, contradicting minimality. This proves the reverse containment. The conclusion also holds when $T=\varnothing$ in a disconnected graph.

Choose two different components $C_1,C_2$ of $G-T$. The three sets $T,C_1,C_2$ are pairwise disjoint. At least one therefore has size at most $\lfloor n/3\rfloor$. Either $T$ itself is small, or $T=N(C_i)$ for a small component. All minimal cuts consequently belong to the union of the following two families: \[ \{S\subseteq V(G):|S|\le n/3\},\qquad \{N(S):S\subseteq V(G),\ |S|\le n/3\}. \] Different small sets may yield the same cut, which only improves the upper bound. We obtain \[ c(n)\le2\sum_{j=0}^{\lfloor n/3\rfloor}\binom nj.\tag{2} \]

3) The entropy estimate without an asymptotic formula

Put $m=\lfloor n/3\rfloor$ and $p=m/n$ for $n\ge3$. For $0\le j\le m$, since $p\le1/2$, \[ p^j(1-p)^{n-j}\ge p^m(1-p)^{n-m}=2^{-nH(p)}. \] Summing the corresponding terms in the binomial expansion of $(p+(1-p))^n=1$ gives \[ \sum_{j=0}^m\binom nj\le2^{nH(p)}\le2^{nH(1/3)}. \] The last inequality follows from $H'(x)=\log_2((1-x)/x)>0$ for $0<x<1/2$. Combining with $2$ and taking $n$th roots proves the upper bound in $1$. In fact \[ 2^{H(1/3)}=\frac{3}{2^{2/3}}<2, \] because cubing the last comparison is $27<32$.

4) An explicit lower construction at every large order

Take two vertices $u,v$ and $m$ internally disjoint paths of length four joining them. Each path has three internal vertices. Choosing exactly one internal vertex from every path gives $3^m$ different cuts. After deletion, each remaining vertex is connected to either $u$ or $v$. Restoring any deleted vertex restores one complete $u$--$v$ path, making the entire graph connected. Thus these cuts are inclusion-minimal, not just separators for a selected pair.

For arbitrary $n$, take $m=\lfloor(n-2)/3\rfloor$ and attach the at most two remaining vertices as leaves at $u$. The same cuts remain minimal, since the leaves stay attached to the $u$ component and join everything when one deleted vertex is restored. Therefore $c(n)\ge3^{\lfloor(n-2)/3\rfloor}$, proving the lower bound in $1$.

5) The unproved step and attribution

Bounds on the liminf and limsup do not imply they are equal. This note does not prove convergence. In particular, minimal separators for a fixed pair and globally inclusion-minimal cuts are different notions on an individual graph; an argument combining fixed-pair separators needs a justified transfer before it can prove the remaining assertion under the convention in Section 1. No such transfer is silently assumed here.

ATTEMPT UNRESOLVED for the convergence step; the strict exponential upper bound is proved. The counting method follows Bradač's small-set argument, expanded here for the stated convention, and the lower example is Seymour's. This is a reconstruction of known bounds, not a new discovery.

6) Sources

https://www.erdosproblems.com/150, checked 23 September 2026. D. Bradač, On a question of Erdős and Nešetřil about minimal cuts in a graph, https://arxiv.org/html/2409.02974v2. No formal verification or reconstruction of the stronger published bounds is claimed.

The estimate credits the proved strict upper exponential rate and lower construction, while withholding completion because convergence has not been established here. It is subjective, not a correctness probability.

7) COMPLETION ESTIMATE

COMPLETION: 60%