First the prove part:
Let's assume v node does not exist which means there is at least two path using totally different nodes from s to t, and the distance is greater than n / 2. This is impossible since you do not even have enough number of nodes for this two path. So this contradicts our assumption there for v node exist.
Second part algorithm:
Use bidirectional BFS. Since v node's exist if you start to search from s and t, they will definitely meet at v nodes. And in the worst case you go thru all the V and E, so it is O(V + E).