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.



determining k-edge-connectivity of a graph
Try:


<http://portal.acm.org/citation.cfm?id=122416>


and the references there.


