Prove a graph with n vertices and with a diameter of 15 has a vertex with degree less than n/6 I need to prove that a graph with n vertices with a diameter of 15 has a vertex with degree less than n/6.
I tried to go with proof by contradiction and see if there's something wrong with the sum of degrees or something like this but found nothing.
Help would be much appreciated
 A: Let $G$ be a graph $n$ vertices and with diameter $15$ in which every vertex has degree at least $\delta$.
Take a vertex $v$ such that there is another vertex at distance $15$ from it.
Notice the graph gets split into $16$ sets $D_0,D_1,\dots, D_{15}$ where $D_i$ is the set of vertices at distance $i$ from $v$.
For each $i$ we have the following: The sum  $|D_{i-1}| + |D_{i}| + |D_{i+1}| > \delta$. This is because otherwise the vertices in $D_i$ would have degree less than $\delta$ (when $i=0,15$ you only get two summands but it's the same thing).
When we add all of these inequalities for the six values of  $i: 0,15,3,6,9,12$ we get $n = \sum\limits_{i} |D_{i-1}| + |D{i}| + |D_{i+1}| > 6\delta$. It follows $\delta < \frac{n}{6}$ as desired.
A: Suppose the degree of each vertex is at least $\frac n6$
Since the diameter of the graph is $15$ there is a path of length $15$ which is the shortest path between the endpoints.  Let the vertices on this path be $v_1$ through $v_{16}$, in order.  Let $V_k$ be the set of vertices not on the path that are adjacent to $v_k$, $1\leq k\leq16$.
$v_1$ cannot be adjacent to any vertex on the path, other than $v_2$, or there would be a shorter  path, so $|V_1|\geq \frac n6-1.$  We also have $|V_4|\geq \frac n6-2$.  Now note that $V_1\cap V_4=\emptyset$, for if $v\in V_1\cap V_4$, we can replace the path $v_1,v_2,v_3,v_4$ by the shorter path $$v_1, v, v_4$.
Continue in this way, and show that the sum of the number of vertices on the path and off the path is greater than $n$.
