The edge connectivity, also called the line connectivity, of a graph is the minimum number of edges 
whose deletion from a graph 
disconnects 
. In other words, it is the size of a minimum
edge cut. The edge connectivity of a disconnected
graph is therefore 0, while that of a connected
graph with a graph bridge is 1.
Let 
be the vertex connectivity of a graph 
and 
its minimum degree, then for any graph,
 |
(Whitney 1932, Harary 1994, p. 43).
Connected bridgeless graphs are 2-edge connected.
The edge connectivity of a graph can be determined in the Wolfram Language using EdgeConnectivity[g]. Precomputed edge connectivities for many named graphs can be obtained using GraphData[graph, "EdgeConnectivity"].
