Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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(diam(G)-1)+2$, when $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 $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(diam(G)-1)+2$ to apply. Am I missing some part here?

Thanks in advance.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
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
My understanding is that the diameter of a graph is the maximum over all pairs of the minimum distance between the pair. Once you have that maximizing pair, all paths joining those two vertices have length at least the maximum (and at least one path has length exactly the maximum). Maybe I'm wrong - find a definition of diameter in some textbook or on the web, and show me. –  Gerry Myerson Feb 8 '12 at 23:10
Oh, now I see that I was wrong about the definition. Thanks for the answer! –  Pavel Feb 9 '12 at 11:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.