Let G(V,E) undirected Graph with n vertices, where every vertex has degree less than $\sqrt{n-1}$. Prove that the diameter of G is at least 3. Let G(V,E) undirected Graph with n vertices, where every vertex has degree less than $\sqrt{n-1}$. Prove that the diameter of G is at least 3.
Well I've thought about proving it by saying G diameter is 2 at most.
Then exists $u,v\epsilon V$ so that $d(u,v)=2$. But i got stuck.
Then i tried Pigeonhole principle, And still nothing.
Any guide-lines please?
 A: The diameter of a graph is the longest shortest path between 2 vertices. Show we want to show that there exists 2 vertices that are distance at least 3 apart.
Hint: Consider any vertex $A$. It is connected to at most $\sqrt{n-1}$ vertices.
Hint: Each of these vertices is connected to at most $\sqrt{n-1} - 1$ vertices that are not $A$.
This describes all the vertices that are distance at most 2 from $A$. How many vertices are there? If we can show that there are less than $n$ vertices, then there must be a vertex that is not distance at most 2 from $A$.
A: similar way but using the fact that every vertex x, connected to less then $\sqrt{n-1}$  vertices.
so given a vertex x, the number of vertices t at distance 2, at most $\sqrt{n-1}\sqrt{n-1}$ with means $t<\sqrt{n-1}\sqrt{n-1}= n-1 $
where t, is the upper bound. so $t-1$ is a "viable" number of vertices at distance 2.
but $t-1=n-2$ with means there is at least one vertex y (excluding x) , at distance greater then 2.
but well either way works, i just like it more this way.
