# Diameter 3 Graph and and minimum maximum degree

• Dec 19th 2011, 04:29 PM
jsndacruz
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!
• Dec 20th 2011, 02:43 AM
emakarov
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.
• Dec 20th 2011, 03:53 AM
jsndacruz
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.
• Dec 21st 2011, 11:45 PM
nikhilbhr
Re: Diameter 3 Graph and and minimum maximum degree
Please share solution if u can
• Dec 22nd 2011, 02:57 AM
emakarov
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}\$.