Printable View
Prove the following claim:
In an undirected and unweighted graph with k vertices, If the length of the shortest path between vertices u and v is greater than k/2 then there must be a vertex w not equal to u or v whose removal disconnects u and v.
I want to do some kind of proof involving the Pigeonhole Principle to show that multiple paths between u and v must share at least one vertex (whose removal would disconnect u and v), but I can't seem to make it work. Any ideas?
Suppose for a contradiction that the result doesn't hold.
So, if we remove a vertex, then there is another path from u to v in the graph. So, it follows that these two paths must create a cycle.
If the paths are internally disjoint (all vertices apart from u and v are distinct), then by hypothesis, each path is of length greater than k/2. So, the cycle has more than k vertices, which cannot happen.
So, any two paths between u and v must share at least one internal vertex
this should be enough to get you started.