Finding vertex-cut using Menger's theorem Menger's theorem states that

A Graph, $G$, is $k$-connected if and only if for every  $x,y \in V(G)$, there exists $k$ pairwise internally disjoint paths.

If I need to find size of vertex cut for any graph using Menger's theorem, it seems like that I need to check all possible pairings of vertices to see how many pairwise internally disjoint paths there are. 
Is there any other version of Menger's theorem to find vertex cut without comparing all possible parings of vertices?  
 A: It's enough to compare only a subset of the pairs (see this answer for an example). But you might still have to compare quite a few pairs.
Write $\kappa(v,w)$ for the size of a minimum $v,w$-cut in $G$. By Menger's theorem, this is equal to $\lambda(v,w)$, the number of internally disjoint $v,w$-paths in $G$, when $v$ is not adjacent to $w$. (If $v$ is adjacent to $w$, then $\kappa(v,w)$ is undefined.) So we can determine $\kappa(v,w)$ for any pair $v,w$ and give a short proof of its value by finding both a cut of size $k$ and a set of $k$ internally disjoint paths.
(We can skip actually finding the cut if all we want is a lower bound on $\kappa(v,w)$, which is the case if we think that we already know the value of $\kappa(G)$. In that case, we just find the right number of paths.)
Let $v$ be any vertex of the graph $G$. If we compute $\kappa(v,w)$ for all vertices $w$ other than $v$, and take the minimum, we have determined the minimum size of most kinds of vertex cuts: the ones in which $v$ is left in one of several connected components, getting separated from some other vertices. 
This leaves as possibilities vertex cuts in which $v$ is one of the vertices that is deleted. But in those cases, at least two of $v$'s neighbors survive and end up in different components: otherwise, there would be no point in deleting $v$. (At least, this is true for minimal cuts.) So we can also compute $\kappa(x,y)$ for all vertices $x$ and $y$ that are adjacent to $v$.
Thus, we are left with the following algorithm (which I get from Algorithm 11 of this article):


*

*Pick any vertex $v$.

*Compute $\kappa(v,w)$ for all other vertices $w$ not adjacent to $v$.

*Compute $\kappa(x,y)$ for all (non-adjacent) vertices $x,y$ which are neighbors of $v$.

*The minimum of all values computed in steps 2 and 3 is $\kappa(G)$. 

