# Minimum vertices to remove from a graph so that no path exists between two given vertices anymore

Given an undirected graph $$G=\{V, E\}$$ with its vertices numbered from $$1$$ to $$V$$, given two vertices $$s$$ and $$t$$ $$(1 \leq s \lt t \leq V)$$, what is the minimum number of vertices (except $$s$$ and/or $$t$$) that we need to remove (we also remove the edges associated with those vertices) so that there doesn't exist any path between $$s$$ and $$t$$ anymore?

If it's difficult to solve under general constraints, can it then at least be solved efficiently in case the maximum possible degree of any vertex in the graph is $$4$$?

My current progress: Maybe it can be solved by using the BFS/DFS numbers obtained from starting BFS/DFS from $$s$$?

The new graph contains vertices $$(s,0),(t,1)$$, and $$(u,0),(u,1)$$ for any $$u \neq s,t$$, as well as the following edges:
• For every $$\{s,u\} \in E$$: the edge $$(s,0) \to (u,1)$$.
• For every $$\{u,v\} \in E$$ (where $$u,v \neq s,t$$): the edges $$(u,0) \to (v,1)$$ and $$(v,0) \to (u,1)$$.
• For every $$\{t,u\} \in E$$: the edge $$(u,0) \to (t,1)$$.
• For every $$u \neq s,t$$: the edge $$(u,1) \to (u,0)$$.
A path $$s \to x \to y \to z \to t$$ in $$G$$ lifts to the following directed path in the new graph from $$(s,0)$$ to $$(t,1)$$: $$(s,0) \to (x,1) \to (x,0) \to (y,1) \to (y,0) \to (z,1) \to (z,0) \to (t,1).$$ As can be seen, in order to realize an $$s$$-$$t$$ path, we need to use the edges $$(u,1) \to (u,0)$$ for all vertices $$u$$ appearing internally in the path.
We now give unit weight to the edges $$(u,1) \to (u,0)$$ and infinite (or large enough) weight to all other edges, and look for a minimum edge cut between $$(s,1)$$ to $$(t,0)$$; this can be solved by computing a maximum flow. A minimum edge cut in the new graph is the same as a minimum vertex cut in $$G$$.