title: Removing a node in an undirected graph that destroys a path between two other nodes
body: <p>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.</p>
  <blockquote>
  <p>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.)</p>
  <p>Give an algorithm with running time O(m + n) to find such a node v.<br />
  (For solution, you can use either plain English or pseudo code.)</p>
  </blockquote>
  <p>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.</p>