There is a natural intuition that two nodes that are far apart in a communication network $($i$.$e$.,$

that are separated by many hops$)$ have a more tenuous connection than two nodes that are close

together $($i$.$e$.,$ that are separated by just a few hops$).$ Consider the following question related to

the susceptibility of paths in communication networks to the deletion of nodes.

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

$($a$)$ 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$.)$