Skip to content

Erdős problem 134

Let ϵ,δ>0\epsilon,\delta>0 and nn be sufficiently large in terms of ϵ\epsilon and δ\delta. Let GG be a triangle-free graph on nn vertices with maximum degree <n1/2ϵ<n^{1/2-\epsilon}. Can GG be made into a triangle-free graph with diameter 22 by adding at most δn2\delta n^2 edges?

Workspace

Open this exact Problem, source revision, and authority Repository in Workbench. This handoff does not clone, switch, upload, or execute anything.

Canvas

public preview
  1. Source#134
  2. ResultNone
  3. Checks0

Reported activity

Work these sources record against this Problem. Source-reported attribution, not reviewed here.

Search problems.science

Find a Problem, Result, source, or page