# Proof that deleting a certain node in a graph where two nodes have a path of length greater than n/2 destroys the path between the two nodes.

I think I understand the problem and why the claim is true, but I just want to make sure my proof is solid. Let me know if there's anything I can do to improve it. Thanks!

Problem: Suppose that an $n$-node undirected graph $G$ contains two nodes $s$ and $t$ such that the distance between $s$ and $t$ is strictly greater than $n/2$. Show that $G$ must contain some node $v$, not equal to $s$ or $t$, such that deleting $v$ from the graph destroys all $s$-$t$ paths. (In other words, the graph obtained from $G$ by deleting $v$ contains no path from $s$ to $t$.)

Proof: If we generate a BFS tree starting at node $s$, node $t$ will be at a level strictly greater than $n/2$ because the path between $s$ and $t$ is strictly greater than $n/2$. The remaining $n-2$ nodes of the tree must go somewhere in at least $n/2$ layers, which will lead to at least one layer containing only a single node $v$. Nodes at layers before and after $v$ cannot connect without going through $v$ because of the property of BFS trees that states that nodes in a BFS tree can only be connected in the corresponding graph if they are in the same or directly adjacent layers. Therefore, the path must go through $v$, and deleting $v$ would destroy the path from $s$ to $t$.

Another way of saying this: for some $k$, $1 \le k \le \lfloor n/2 \rfloor$, there is only one node at distance $k$ from $s$ (otherwise, counting $s$, $t$ and at least $2$ nodes at each $k$ you'd nave at least $2 + 2 \lfloor n/2 \rfloor > n$ vertices).
Every path from $s$ to $t$ must pass through a node at distance $k$ from $s$, so if you delete the only such node you no longer have such a path.