Confusion related to a graph problem

Question

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?

Answer 1

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

  1
 / \
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.

Answer 2

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$?