Diameter 3 Graph and and minimum maximum degree

**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!

Re: Diameter 3 Graph and and minimum maximum degree

Quote:

Originally Posted by

**jsndacruz** 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))

Maybe n^(4/3)?

You could try using the inequality related to Moore graphs.

Re: Diameter 3 Graph and and minimum maximum degree

Wow, I've never heard of that before. Thanks! I have to study for linear now, but I'll tackle this problem again tomorrow night.

Re: Diameter 3 Graph and and minimum maximum degree

Please share solution if u can

Re: Diameter 3 Graph and and minimum maximum degree

Assuming the contrary, the maximum degree is $\displaystyle < n^{1/3}$. Then, using the equality from the link above, we get that $\displaystyle n < 1+n^{1/3}(1+n^{1/3}-1+n^{2/3}-2n^{1/3}+1)$. 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 $\displaystyle <n^{1/3}$.