1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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