Skip to content

Erdős problem 618

For a triangle-free graph GG let h2(G)h_2(G) be the smallest number of edges that need to be added to GG so that it has diameter 22 and is still triangle-free. Is it true that if GG has maximum degree o(n1/2)o(n^{1/2}) then h(G)=o(n2)h(G)=o(n^2)?

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/618.lean

Formal Conjectures

FormalConjectures/ErdosProblems/618.leanErdos618.erdos_6185 linesExact file
True ↔  ∀ (G : (n : ℕ) → SimpleGraph (Fin n)),    (∀ (n : ℕ), (G n).CliqueFree 3) →      ((fun n => ↑(G n).maxDegree) =o[Filter.atTop] fun n => ↑n ^ (1 / 2)) →        (fun n => ↑(Erdos618.h2 (G n))) =o[Filter.atTop] fun n => ↑n ^ 2
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Proof manifests naming this Problem

  • Jayyhk Erdős Leanjayyhk:erdos:618
  • PLBY Lean proofsErdosProblems.Erdos618

Reported activity

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

Continue

Start a contributionBrowse the source filesOpen the collection entry

Search problems.science

Find a Problem, Result, source, or page