# Graph question concerning components.

## 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).

• @Casteels I'm sorry I don't understand what you mean
– Ogen
Commented Aug 13, 2014 at 11:03
• It's not clear to me what is meant by saying that the graph is "of order n and size m" and "contains two vertices $s$ and $t$ of distance more than $n=2$." Are $s$ and $t$ at distance more than the order of the graph? Or of distance more than $2$? Or of distance more than the order which is greater than $2$? Perhaps you can clarify, @Ogen . Commented Aug 13, 2014 at 12:01
• @Ogen I know these definitions, my question is about what the statement that "$s$ and $t$ are at distance more than $n=2$", where $n$ is the order, means in this particular problem. It seems like a rather ambiguous statement. Commented Aug 13, 2014 at 12:04
• To be more precise "distance" between $s$ and $t$ is the length of the shortest path between $s$ and $t$. But how can two vertices have distance larger than the number of vertices? Commented Aug 13, 2014 at 12:06
• I'm so sorry, its not n=2, it's n/2. I edited the post.
– Ogen
Commented Aug 13, 2014 at 12:09

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.