# Graph: vertex connectivity and edges connectivity

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 ?

## 1 Answer

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.