Erdős Problem #150
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A minimal vertex separator of a graph is a set of vertices whose removal disconnects some pair of previously connected vertices, but for which no proper subset does the same. Let \(c(n)\) be the maximum number of distinct minimal vertex separators in any graph on exactly \(n\) vertices.
Erdős and Nešetřil asked whether the exponential growth rate
exists and satisfies \(\alpha<2\). They separately asked whether a particular construction attains \(c(3m+2)=3^m\). The main rate-of-growth question and this proposed exact finite formula must be distinguished.
A small example
Join two vertices \(s,t\) by \(m\) internally vertex-disjoint paths of length four. Each path has three internal vertices, so the graph has \(3m+2\) vertices. To disconnect \(s\) from \(t\), one must remove at least one internal vertex of each path. Choosing exactly one of the three internal vertices on every path gives \(3^m\) different minimal \(s\)–\(t\) separators.
This construction gives \(c(3m+2)\ge3^m\). It does not show that no other graph with the same number of vertices has more separators. The stronger equality is now known to be false.
What is known
PROVED: the exponential rate exists and is strictly below two. Fomin, Kratsch, Todinca and Villanger (2008) obtained an upper constant \(1.7087\). Fomin and Villanger (2012) and later simplified work by Gaspers and Mackenzie improve it to the golden ratio
Gaspers and Mackenzie also give the currently reported lower estimate \(\alpha\ge1.4457\), which exceeds \(3^{1/3}\approx1.4422\) and disproves the proposed equality \(c(3m+2)=3^m\) for all \(m\). The maintained Erdős #150, edited June 2026, attributes the limit-existence argument to Bradač (2024). The primary full algorithms and separator enumeration proofs have not been independently recreated.
GCL's current state
The pinned catalogue and maintained problem classify the main question as PROVED. The authenticated original issue is #1419. The distinction between existence of \(\alpha\), the bound \(\alpha<2\), and the rejected exact \(3^m\) formula is retained. A source report or Lean statement alone does not certify those external combinatorial proofs under GCL governance.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded task generates the \(3m+2\) path construction for \(m=1,2,3\) and enumerates its minimal \(s\)–\(t\) vertex separators. Acceptance: exactly \(3^m\) separator choices in that family, and an explicit demonstration that this supplies a lower bound rather than universal equality. Separately verify the logical passage from published exponential upper and lower estimates to the claimed rate under the source's existence theorem.
Sources and claim boundaries
- Erdős #150, source references [FKTV08], [FoVi12], [GaMa18] and [Br24].
- GCL original issue #1419.
No new optimal separator-count theorem, independently reconstructed growth-limit proof or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1419 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.