1. ## Graph Theory Proof

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?

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