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).
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!