Given a $k$-regular graph, its diameter is bounded by $O(n/k)$ where $n$ is the number of nodes and $k$ is the degree of each node.
Is there any straight-forward way to prove this result?
[Math] Diameter of $k$-regular graph
graph theory
Related Solutions
The answer is yes.
Pick two copies of your graph, and draw them one next to each other.
Now, on the graph on the left erase the rightmost outside edge. On the graph on the right erase the leftmost outside edge.
Connect the top vertices and the bottom vertices of the two graphs.
It is easy to also produce such graphs from $3,4,..., n$ copies of your graph.
Best Answer
I won't give a complete answer, but a hint that should be enough.
Let $d$ be the diameter of a graph $G$ and let $u, v$ be vertices satisfying $dist(u,v) = d$. Now let $S_i$ be the set of vertices $w$ such that $dist(u,w) = i$. Finally, consider a shortest path $P$ between $u$ and $v$.
Remember that $G$ is $k$-regular. Note that the neighbors of the vertex in $S_i \cap P$ need to be in $S_{i-1}$, $S_i$ and $S_{i+1}$ (otherwise you would have a contradiction with the minimality of $P$) and hence $|S_{i-1}| +|S_{i}| + |S_{i+1}| \geq k$. What are the consequences of $|S_{i-1}| + |S_{i}| +|S_{i+1}| \geq k$?