Removing a node in an undirected graph that destroys a path between two other nodes

Question

I need help with this problem that I'm currently working on, which involves finding a node v in an undirected graph that, when removed, will destroy all paths between two other nodes s and t.

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. (In other words, the graph obtained from G by deleting v contains no path from s to t.)

Give an algorithm with running time O(m + n) to find such a node v.
(For solution, you can use either plain English or pseudo code.)

My understanding of this is that the solution would involve creating a breadth-first search that finds the node v and removes it, but I'm not certain of how to prove that removing the node exists in the first place such that removing it would destroy all s-t paths.

Answer 1

First the prove part:

Let's assume v node does not exist which means there is at least two path using totally different nodes from s to t, and the distance is greater than n / 2. This is impossible since you do not even have enough number of nodes for this two path. So this contradicts our assumption there for v node exist.

Second part algorithm:

Use bidirectional BFS. Since v node's exist if you start to search from s and t, they will definitely meet at v nodes. And in the worst case you go thru all the V and E, so it is O(V + E).