1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.