0
$\begingroup$

So the number of edge disjoint u,v paths in a graph is x. Doing this problem, I thoguht back to Menger's theorem, and thought that the graph is x-edge-connceted and so the number of cut sets between any two vertices is also x. However I'm not sure how to find find out anything about the vertex connectivity since all I was given was the number of edge disjoint paths.

$\endgroup$
0
$\begingroup$

I think this is because there is nothing you can find out in general i.e. you can have many edge disjoint paths for every pair of vertices but it is still possible for the graph to have vertex connectivity $1$.

For example suppose you have two complete graphs $G, G'$ on $n$ vertices each. Now let's merge these two graphs in the following way: Construct a new vertex $v$ and connect $v$ with every vertex in $G$. Also connect $v$ with every vertex in $G'$. Call this new graph $G''$. If you choose any two vertices $u, w$ from $G''$ you will find that there are always at least $n - 1$ (actually it is even more, $n$ would work too for example) edge disjoint paths between $u$ and $w$. But obviously the graph $G''$ has vertex-connectivity $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.