Question on Graph Connectivity Now this question is on graph connectivity and I still can't get my head around these graph theory questions. Now we've been given an n-node graph which is represented by $G=(V,E)$ and two nodes $s$ and $t$ are in $V$, where all the paths between $s$ and $t$ are strictly greater than $n/2$. Show that a node $v$, not equal to $s$ or $t$, exists, removing which from $G$ would eliminate all $s-t$ paths. 
And next we have to devise an algorithm with runtime $O(n + m)$, where $m$ is the number of edges, which can find such a node v.
Solution: Now I tired making diagrams to figure out what the Graph may look like. One observation I made was that the nodes $s$ and $t$ can't be in a cycle because then one of the paths from $s$ to $t$ won't be strictly greater than $n/2$. It's fairly obvious. Lets have a graph which is just a cycle. There would be $n$ nodes and $n$ edges. Hence one of the two paths would be shorter than $n/2$.
Hence there are two options: 


*

*There is only one path from $s$ to $t$ in which case we can just remove any node between those two.

*In the other case there is one path from $s$ to $t$ and one path from either $s$ and $t$ to any vertex in the path from $s$ to $t$. Hence we get a cycle from $s$  or $t$ to that specific vertex $v$ back to $s$ or $t$. Hence we can remove that specific node between $s$ and $t$ to disconnect all the paths.
In that algorithm I though one can just walk from $s$ to $t$ and figure out the vertex with maximum degree and remove it.
Is my solution correct? Thanks in advance.
 A: We show by strong recurrence on $n$ the number of nodes that for every graph $G=(V,E)$ and two nodes $s$ and $t$ in $V$, where all the paths between $s$ and $t$ are strictly greater than $n/2$ there is a node $p$ that is on all paths from $s$ to $t$.
Base case $n=3$: Let $G=(\{s,t,p\},E)$ be such that all the paths between $s$ and $t$ are strictly greater than $3/2=1$ the only possibility for $E$ is that $E=\{(s,p),(p,t)\}$ and thus $p$ is on all paths from $s$ to $t$.
Similarly for $n=4$ we obtain that the only possible graph is the line hence the property is satisfied. 
Assume that the property holds for every $k\leq n$. 
Let $G=(V,E)$ be a graph with $n+1$ nodes and $s$ and $t$ two nodes in $V$, such all the paths between $s$ and $t$ are strictly greater than $(n+1)/2$.
We distinguish two cases: 


*

*either there is an unique node $p$ such that $(s,p)\in E$. We have thus that $p$ belongs to all the paths from $s$ to $t$

*There exists two node $s_1$ and $s_2$ such that $(s,s_1)\in E$ and $(s,s_2)\in E$. Consider the graph $G'=(V',E')$ obtained from $G$ by contracting the two edges i.e. $V'=V\setminus\{v_1,v_2\}$ and $E'= E\cap (V'\times V')\cup \{ (s,v)\mid (s_1,v)\in E,v\in V'\}\cup \{ (s,v)\mid (s_2,v)\in E,v\in V'\} $. Assume, by contradiction, that there is a path in $G'$ from $s$ to $t$ on length $l\leq (n-1)/2$ this path gives you a path in $G$ ( by expending the contracted edges) of length $l'\leq l+1 \leq (n-1)/2+1 = (n+1)/2$. Contradiction.


hence $G'$ have $n-1$ nodes and all the paths from $s$ to $t$ are strictly greater than $(n-1)/2$. Hence by hypothesis there exist a node $p\in V'$ that is on all path from $s$ to $t$. And by construction this node is also on all paths from $s$ to $t$ in $G$.
This proof also gives you for free an algorithm to find such node. Either there is an unique edge leaving $s$ and you have your node, or there are at least two edges leaving $s$: you contract two of them and start again.
I hope it helps.
A: @wece
Small fix needed in your proof:
In your "case two" you are deleting two vertices from $V$ (I am assuming that you meant $s_1$ and $s_2$, not $v_1$, $v_2$) and then you are saying that $G'$ has $n-1$ nodes. If you are contracting one edge, say $AB$ to vertex $A$, then you are eliminating one node (namely, $B$) and transforming all the edges $BV$ to $AV$. 
So: $n$ changes to $n-2$, and all the paths from $s$ to $t$ are now obviously longer than $(n-2)/2$ = $n/2$-1. Also -- edge $s_1s_2$, if it existed, needs to be eliminated upon contraction. Thankfully, it could not have been present in any shortest path from $s$ to $t$.
