0
$\begingroup$

I know that a graph is $k-$ connected if any two vertex can be connected by $k$ independent path. This is what we call the vertex connectivity. But what is the edges connectivity ?

$\endgroup$
2
$\begingroup$

What you call $k$-connectivity is what we usually call Menger's theorem. $k$-connectivity (in terms of vertices) means that if we delete any $k-1$ vertices then the graph is still connected. In terms of edge connectivity, if a graph is $k$-edge connected, then we can delete any $k-1$ edges and not disconnect the graph.

See: http://en.wikipedia.org/wiki/Menger%27s_theorem for details about Menger's theorem.

$\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.