Skip to content

Erdős problem 619

Start work

Erdős Problem 619 [EGR98, Er99]: For a triangle-free graph GG let hr(G)h_r(G) be the smallest number of edges that need to be added to GG so that it has diameter rr (while preserving the property of being triangle-free). Is it true that there exists a constant c>0c>0 such that if GG is a connected graph on nn vertices then h4(G)<(1−c)nh_4(G)<(1-c)n?

Sources

The source's own material, retained exactly.

7 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

619.lean

Retained formal statement4 of 7

Erdős, Gyárfás and Ruszinkó [EGR98]: every connected triangle-free graph on a finite vertex set can be extended, by adding edges, to a triangle-free graph of diameter at most 33. This shows that the infimum defining minNewEdges r G ranges over a nonempty set for every 3 ≤ r.

FormalConjectures/ErdosProblems/619.leanErdos619.erdos_619.variants.add_edges_diam_three2 linesExact file
∀ {V : Type u_1} [Fintype V] (G : SimpleGraph V),  G.Connected → G.CliqueFree 3 → ∃ H, G ≤ H ∧ H.CliqueFree 3 ∧ H.ediam ≤ 3
SolvedStatement only, no proof