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.
Proving a graph contains a single node on a given level
1
$\begingroup$
graph-theory
-
0Is the graph a tree? – 2012-10-04
1 Answers
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.