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

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

1 retained statement2415f78e850a

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

Search problems.science

Find a Problem, Result, source, or page