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][1].


  [1]: https://en.wikipedia.org/wiki/Menger's_theorem