Status
On this page
Status
Topics
Status
On this page
Status
Topics
A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let be the maximum number of minimal cuts a graph on vertices can have.
Does for some ?
Source: erdosproblems.com/150
An accepted solution exists. The statement is true.
PROVED (LEAN). The limit exists and satisfies (the site's interval), so . Existence: Proposition 2 of Bradač's note (J. Graph Theory 108 (2025), no. 4, 817--818, published online 8 December 2024, refereed; cited from the arXiv v2), by Fekete's lemma for the marked-pair separator count , transferred to by the paper's displayed sandwich , whose right inequality is immediate and whose left inequality the paper asserts as "Clearly" without argument (recorded as a proof-coverage gap, not a dispute). The bound: every minimal cut is a minimal separator, so , and by Fomin and Villanger's Theorem 1 (Combinatorica 2012, refereed; cited from the arXiv v2), whose proof's estimate has the golden ratio as its base (p. 7), reproved as by Gaspers and Mackenzie's Theorem 1 (J. Graph Theory 2018, refereed); Bradač's Theorem 1 gives , , directly for minimal cuts; and the first proof of is of Fomin, Kratsch, Todinca and Villanger (SIAM J. Comput. 2008, refereed), as the journal's abstract states it and as Bradač's note and Gaspers and Mackenzie attest. These three separator bounds are accepted partial claims on the bound half of the question, recorded on the claim pages of Fomin, Kratsch, Todinca and Villanger, Fomin and Villanger and Gaspers and Mackenzie. The lower bound is Seymour's construction in Erdős's paper, and is the lower bound the site and Bradač attribute to Gaspers and Mackenzie's Theorem 2 for minimal separators, as the published J. Graph Theory version states it ( in its abstract); that version is not held and its proof is unchecked, while the arXiv v2 prints ; the transfer to is through the same sandwich. The site's curator accepted the resolution with the label PROVED (LEAN) on 31 March 2026, crediting Bradač's note; the external Lean file behind the label declares itself a formalization of Bradač's argument and works with the separator count, not the collection's minimal-cut count (Formalization). Bradač's note is the accepted full claim, recorded on its claim page (Bradač, 2024), which carries the Lean file as a formalization link, and the frontmatter standing is derived from it.