# Proving a graph contains a single node on a given level

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.

-
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

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.

-