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.


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?


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):

 / \
2 - 3 

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.

  • $\begingroup$ I didn't get how this is a counter example. Any pair of nodes are at a distance 1 which is less than n/2=1.5. So obviously there is not cut off points $\endgroup$ – user61169 Feb 6 '13 at 4:28
  • $\begingroup$ @user61169: You're asking why the $\geq n/2$ criterion is necessary. To see why it's necessary you need to stress-test situations where $<n/2$. It's necessary precisely because there are counterexamples if you are in the $<n/2$ situation. $\endgroup$ – Alex R. Feb 6 '13 at 4:31
  • $\begingroup$ Can u give me an example where it is strictly greater than n/2 and there is a cut off point? $\endgroup$ – user61169 Feb 6 '13 at 4:37
  • $\begingroup$ How about your example, the numbers 5 and 7. Indeed, if you pick ANY two vertices in your example such that the distance between them is bigger than n/2, then there MUST exist a vertex that cuts them off. It just so happens though that in your example, some points with distance smaller than n/2 can also be cutoff. The point is you are assured 100% that you can cut the two points off with distance at least n/2. Any stronger result than this will heavily depend on extra structure in your graph. $\endgroup$ – Alex R. Feb 6 '13 at 4:44

You are confusing the direct and converse implication...

It's like hearing a Theorem that "all penguins are black" and trying to argue that not all black things are penguins.

The Theorem only sais that if you can find two vertices with distance at least $n/2$ then something happens.

If two vertices have distance at least $n/2$, then you can use the Theorem...

If two vertices have distance less than $n/2$ the theorem says NOTHING. So in your graph the theorem sais absolutelly nothing about vertices 1 and 7....

And the reason why is necessary is this: consider the cycles $1,2,3$ and add vertices $4,5$ connected by $14$ and $25$. What is the distance between $4$ and $5$?

  • $\begingroup$ @N.S. the distance between 1 and 5 is 1. It is one hop away. The node 2 is between 1 and 5. So whats the point. I didn't get it $\endgroup$ – user61169 Feb 6 '13 at 4:29
  • $\begingroup$ @user61169 Fixed the question... The point is that $\frac{n-1}{2}$ doesn't work... $\endgroup$ – N. S. Feb 6 '13 at 4:30
  • $\begingroup$ Actually. I found that the solution to find it is something like this. BFS starting at node s until you find a node v that is in a layer by itself and delete that node thus disconnecting and possible connection from s to t. I didn't get how this is valid. How it actually is the solution. Any clarifications? $\endgroup$ – user61169 Feb 6 '13 at 4:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.