Determine the diameter of a graph of order $n \geq 3$ where $\delta (G) \geq \frac{n-1}{2}$. 
Let $G$ be a graph of order $n \geq 3$ such that $\delta (G) \geq \frac{n-1}{2}.$ Determine the diameter of $G$.

So $\delta (G)$ is the minimum degree of a vertex in the graph $G$. How can I approach such a question? I know that the diameter of a graph is the "largest shortest-path" between any pair of vertices in a graph, or in other words, the maximum distance between all possible pairs of vertices in $G$. Also, do I have to make use of the maximum degree of $G$ to solve this problem?
 A: Start drawing up a few small examples, like for $n = 3,4,5,6$. Some things that you should realize as you do this are that,

*

*$G$ must be connected,


*the case where $n$ is odd might be tougher than when $n$ is even, and


*the graph diameter is probably $2$.
After you play with the small examples and get a feel for what the diameter probably is, you should start writing a proof and hope it works out.

For a graph of order $n$, designate some vertex $v$ of the graph. Let $A$ be the set of vertices adjacent to $v$, and let $B$ be the set of vertices not adjacent to $v$. Note that $|A| \geq \frac{n-1}{2}$, and so  $|B| \leq \frac{n-1}{2}$. Take an arbitrary vertex $b \in B$. Note that $b$ must be adjacent to some vertex in $A$. This is true because otherwise it's neighbors could only lie in $B$, giving it a max of $\frac{n-1}{2}-1$ neighbors, and contradicting the minimum degree of $b$ being $\frac{n-1}{2}$.
So the length of a path from $v$ to some other vertex is $1$ if that other vertex is in $A$, and $2$ if that other vertex is in $B$. So the graph's diameter is $2$.

