Question
Suppose that an undirected graph of order $n$ and size $m$ contains two vertices $s$ and $t$ of distance more than $n/2$. Show their exists a vertex $v$, not equal to $s$ or $t$, such that $s$ and $t$ are in different components of $G$ \ $v$. Give an algorithm with running time $O(n + m)$ to find such a vertex $v$.
I'd just like some help understanding this question, I have drawn a graph in paint, is this an example of this problem?
So it looks like s and t are in different components if you take out v. Also, I'm not sure if G\v actually means taking out v. I read on wiki that the \ operator can be translated to G or not v in this case.
Either way, how can I come up with an algorithm for this problem. Am I right in saying that the vertex v has to be a point that splits components? (notice how all vertices go through v, it acts like a chokepoint so when you remove it you get left with two components).
The existence of $v$ isn't so bad. Presumably $n\geq 3$ is also assumed here.
If $s$ and $t$ are already in different components of $G$, then just take $v$ to be any vertex besides $s$ or $t$.
If $s$ and $t$ are in the same component and no such $v$ exists, then by Menger's theorem there are two paths $P_1,P_2$ from $s$ to $t$ that share no internal vertices. But then at least how many vertices in total do $P_1$ and $P_2$ use?
As for an algorithm, I believe the idea is to construct a depth-first search tree rooted at $s$ and think about the non-tree edges.