# determining k-edge-connectivity of a graph

Is there any remotely efficient way to determine whether a graph can be disconnected by the removal of fewer than k edges, or even one that has a lower asymptotic complexity than just trying each set of k-1 edges?

If it helps, you can assume the graph is k-regular that k is much smaller than the number of vertices.

-
There is a really nice algorithm due to Nagamochi and Ibaraki which does not use flows, and is easy to implement. I could not quickly find a nice description online, but the paper is: Computing Edge-Connectivity in Multigraphs and Capacitated Graphs SIAM J. Discrete Math. Volume 5, Issue 1, pp. 54-66 (February 1992) –  Chris Godsil Jul 4 '10 at 15:48

Generally $k$-connectivity is computed using max-flow min-cut algorithms. I cannot quote you complexities off the top of my head, but you should be able to find the number of edges that disconnect any pair of nodes $(x,y)$, and then iterate over all $O(n^2)$ pairs. A key result here that underpins these algorithms is Menger's Theorem.
If G is undirected, you can do better than finding max-flow min-cut over all pairs of vertices. Since you are guaranteed that any given vertex $s$ is contained in one of the partitions of a minimum cut, you can choose any arbitrary vertex $s$ and compute the max flow/min cut to each other vertex $t$. The minimum of these values is the min cut of the graph with cardinality $lambda(G)$, the edge connectivity of G. –  Justin Melvin Jul 4 '10 at 14:01