Maybe n^(4/3)?
You could try using the inequality related to Moore graphs.
Problem:
Let G be a graph on n >= 4 vertices such that for any two vertices, v_1 and v_2, there is a path of length <= length 3 with endpoints of v_1 and v_2. Prove that G has a point of degree >= n^(1/3).
My attempt:
I would like to prove the result by contradiction. Assume that all vertices have degree strictly less than n^(1/3). Then the sum of degrees is less than n(n^(4/3)) and the number of edges is strictly less than (1/2)n^(4/3). I would like to prove that then there are not enough edges to connect all vertices in the manner described, but don't know where to turn to figure out what the minimum number of edges needed would be.
Any suggestions would be appreciated. Thanks in advance!
Maybe n^(4/3)?
You could try using the inequality related to Moore graphs.
Assuming the contrary, the maximum degree is . Then, using the equality from the link above, we get that . Solving this gives n < 4.2, i.e., n <= 4. By assumption, n >= 4, so we get a contradiction except in the case n = 4. You must show manually that when n = 4, the maximum degree cannot be .