Erdős Problem #618 — Adding Edges to Obtain Triangle-Free Diameter-Two Graphs
Statement
For a triangle-free graph on , define to be the smallest number of edges that must be added to so that the resulting graph remains triangle-free and has diameter at most ; that is, every two distinct vertices are adjacent or have a common neighbor. If no such supergraph exists, take . Is it true that for every sequence of triangle-free graphs , if the maximum degree satisfies then Equivalently, for every family assigning a simple graph on to each , if every is triangle-free and then
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.