I have this question related to this graph problem
Suppose that an n-node undirected graph G = (V , E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths
Why is it that the distance between s and t is strictly greater than n/2.
1-2-3-4-5 | 6 | 7
Consider the above graph. 7 is one hop aways from 1. Total number of nodes n = 7. n/2=3. Even if 7 is less than n/2 hops away from 1, there is a node 6 which will separate 1 and 7 when cut. So I didn't get what this n/2 criteria is. I am not being able to visualize. Why is it necessary. Can anyone please clarify?