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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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|cite|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
@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

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.