Erdős problem 150

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

The source's own material, retained exactly.

5 retained statements36c6d0fef71a

FormalConjectures/ErdosProblems/

150.lean

Retained formal statement4 of 5

Seymour observed that $c(3m+2)\geq 3^m$ , as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

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

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

SolvedStatement only, no proof