Skip to content

Erdős problem 584

Must every graph with nn vertices and δn2\delta n^2 edges contain large subgraphs in which every two edges lie on specified short cycles? A dense high-girth construction refutes the statement when δ\delta may shrink with nn.

Sources

The source's own material, retained exactly.

1 retained statement36c6d0fef71a

Open selected source

Retained excerpts/

VibeMathed

Retained source excerpt1 of 1

Must every graph with $n$ vertices and $\delta n^2$ edges contain large subgraphs in which every two edges lie on specified short cycles? A dense high-girth construction refutes the statement when $\delta$ may shrink with $n$.

Open exact source location