Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Given that a graph contains a path between two nodes (A,Z) that has a distance which is strictly greater than n/2, is there a way of showing that the graph must contain a level in which there is only one node? If yes, how? More specifically, this node should exist between the path from node A to node Z.

share|cite|improve this question
I assume $n = |G|$? But, you should say this. – Graphth Oct 4 '12 at 16:34
What do you mean by 'level'? Minimal distance from $A$, or what? – Berci Oct 4 '12 at 16:50
Is the graph a tree? – Alexander Gruber Oct 4 '12 at 22:01
up vote 1 down vote accepted

Suppose there are $\ell$ levels (which I interpret as per Berci's comment: to be non-empty sets of vertices of minimum distance $i$ from $A$, for some $i$ [excluding the possibility of a level containing $A$ itself, which would make the question trivial]).

Since $B$ has minimum distance greater than $n/2$, we know $\ell>n/2$ (each vertex on a shortest path from $A$ to $B$ would be in a different level). If each level had $2$ or more vertices, then we would have at least $2\ell>n$ vertices, giving a contradiction. Hence, there must exist some level with $1$ vertex.

share|cite|improve this answer

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.