KEdgeConnectedGraph

A graph is k-edge-connected if there does not exist a set of k - 1 edges whose removal disconnects the graph. The maximum edge connectivity of a given graph is the smallest degree of any node, since deleting these edges disconnects the graph. Complete bipartite graphs have maximum edge connectivity. k-edge-connectedness graph checking is implemented in the Wolfram Language as KEdgeConnectedGraphQ[g, k]. The following table gives the numbers of k-edge-connected graphs for n-node graphs.

cyclic edge connectivity | edge connectivity | edge cut | graph bridge | k-connected graph