# Min. number of vertices in graph as function of $\kappa(G)$ and $\operatorname{diam}(G)$

Question I found in "Introduction to Graph Theory" by Douglas B. West:

Let $G$ graph on $n$ vertices with connectivity $\kappa(G)=k \geq 1$. Prove that $$n \geq k(\operatorname{diam}(G)-1)+2$$ where $\operatorname{diam}(G)$ is the the maximal (edge) distance between a pair of vertices in $G$

Seems easy and I've seen the answer, too, which goes the same as thought: by taking the vertices the end vertices of the path of length $\operatorname{diam}(G)$, and applying Menger's Theorem. I'm having a hard time understanding one part - it seems like all the paths need to be of the same length for the $n \geq k(\operatorname{diam}(G)-1)+2$ to apply. Am I missing some part here?

-

Let's write $d$ for the diameter of $G$. Then there is some pair of vertices such that one path between them has exactly $d$ edges, and each path between them has at least $d$ edges. Menger says there are $k$ independent paths. So the number of vertices is at least $k(d-1)+2$.
I'm not sure why you think the paths all have to be the same length. They just have to have length at least $d$ - and, they do.
I don't think that all the paths have the same length, but that the maximal path length is $d$ (or am I misunderstanding the notion of $diam(G)$?). –  Pavel Feb 8 '12 at 19:25
@GerryMyerson is $k$ stand for the number of component in $G$? I also struggle on this problem, and I'm not sure I understand how you get from there are $d$ internally disjoint $u-v$ paths, to number of vertices is $n \geq k(G) [d-1]+2$? Maybe I misundertand something in Menger's theorem –  Diane Vanderwaif Oct 12 '14 at 14:51
$k$ stands for the connectivity of $G$, which is not the number of components. I don't have $d$ internally disjoint paths, I have $k$ internally disjoint paths, each path having at least $d$ edges. –  Gerry Myerson Oct 13 '14 at 0:26