# Diameter of $k$-regular graph

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?

-
Is this true? Is it bounded by n/k or O(n/k)? – Vinicius dos Santos Apr 5 '13 at 8:36
It is actually not bounded by n/k. Take for example the following 3-regular graph: start with one vertex adjacent to all the vertices of a path on 3 vertices. Join the two extremity to an other vertex, says u. do a copy of this graph with v the copy of u and join u and v. This graph has diameter 5, 10 vertices and degree 3. This example can easily be generalized. The correct bound seems to be something like $3n/k$ (see discuss.fogcreek.com/joelonsoftware3/…) – Aline Parreau Apr 5 '13 at 8:42
Sorry, it should be O(n/k) – Jeremy Apr 5 '13 at 8:52
If $k$ is fixed as $n \rightarrow \infty$, then $n=O(n)=O(n/k)$. I suspect this is not what you want either. – Douglas S. Stones Apr 5 '13 at 12:56

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$?
I understand your idea. But I guess it is also possible for a vertex in $S_i$ to have a neighbour also in $S_i$. So $|S_{i-1}| + |S_i| + |S_{i+1}| \geq k$. – Jeremy Apr 5 '13 at 9:31