Minimum-size conjecture for 3-connected graphs with cyclic neighborhoods

Let GG be a graph of order nn and size mm. Assume that GG is 3-connected and that every neighborhood of a vertex contains a cycle. Minimum-size conjecture. Then

m73(n1).m\geq \frac{7}{3}(n-1).

The question concerns graphs with no forest cut: such graphs are necessarily 3-connected and have a cycle in every vertex neighborhood. The family GkG_k described in the paper has 3k+43k+4 vertices and 7k+77k+7 edges and satisfies these structural conditions, motivating the proposed lower bound; whether any such graph can have fewer edges remains open.

Sources & referencesView supporting material

Primary source

Vsevolod Chernyshev, Johannes Rauch and Dieter Rautenbach, “Forest Cuts in Sparse Graphs”, arXiv:2409.17724 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.