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.

  • 0
    Is the graph a tree?2012-10-04

1 Answers 1

1

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.