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?
Best Answer
You are trying to prove:
"there exist $s,t$ with $distance(s,t)\geq n/2$ $\Longrightarrow$ there exists $v$ which cuts off $s,t$
It sounds like you don't understand why $\Longleftarrow$ doesn't hold as well. For this you need to exhibit at least one counterexample. Take the complete graph of 3 vertices (a triangle):
where the distance between any pair of nodes is 1, yet $n=3$ so $n/2=1.5$. Clearly 1,3 will remain connected if you remove 2.
To generalize this example to any $n$, think of $K_n$, the complete graph on $n$ vertices.