Skip to content

Erdős problem 150

A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let c(n)c(n) be the maximum number of minimal cuts a graph on nn vertices can have.

Sources

The source's own material, retained exactly.

5 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

150.lean

Retained formal statement3 of 5

The current best-known bounds on α\alpha are 1.4457≤α≤1+52≈1.618.1.4457\leq \alpha \leq \frac{1+\sqrt{5}}{2}\approx 1.618. The lower bound is due to Gaspers and Mackenzie [GaMa18].

FormalConjectures/ErdosProblems/150.leanErdos150.erdos_150.variants.lower_bound1 lineExact file
∀ (α : ℝ), Filter.Tendsto (fun n => ↑(Erdos150.maxMinimalCuts n) ^ (1 / ↑n)) Filter.atTop (nhds α) → 1.4457 ≤ α
SolvedStatement only, no proof