Erdős problem 150 · problems.science

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

Sources

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

150.lean

Retained formal statement2 of 5

Asked by Erdős and Nešetřil, who also ask whether $c(3m+2)=3^m$ .

Note that the lower bound $1.4457\leq \alpha$ of Gaspers and Mackenzie [GaMa18] provides a negative answer to the above question of Erdős and Nešetřil.

FormalConjectures/ErdosProblems/150.leanErdos150.erdos_150.variants.erdos_nesetril1 lineExact file

1False ↔ ∀ (m : ℕ), Erdos150.maxMinimalCuts (3 * m + 2) = 3 ^ m

SolvedStatement only, no proof

Sources

Search problems.science