Hints on proving bottlenecked node exist in a undirected graph during shortest path find

Question

Given that I have a graph G = (V, E) if the distance from s to t is strictly larger than |V|/2, there must be a bottleneck node on in the graph. A bottleneck node is a node defined to be: when removed, s and t will no longer be connected.

I know the general algorithm to this problem, but I can't figure out a way to prove this. I keep on running back to either circular logic or just ending up giving the algorithm to find the bottleneck node.

Any hints on now to prove this using direct proof, prove by contradiction, or pigeonholed principle?

Answer 1

Proof by contradiction:

Let s and t have a minimal path P1 of length |P1| > |v|/2. Assuming that there's no bottleneck node in P1 means that there exists an alternative, disjoint path P2 between s and t (sharing only the nodes s and t). Since P1 has the shortest length, we know that |P2|>=|P1|.

Now, the total number nodes in the graph must be at least the number of nodes in the union of P1 and P2:

|v| >= |P1|-1 + |P2|-1 + 2 = |P1| + |P2| >= 2|P1| > |v|

And this is the contradiction.