connectivity | line connectivity

The edge connectivity, also called the line connectivity, of a graph is the minimum number of edges λ(G) whose deletion from a graph G disconnects G. 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 κ(G) be the vertex connectivity of a graph G and δ(G) its minimum degree, then for any graph, κ(G)<=λ(G)<=δ(G) (Whitney 1932, Harary 1994, p. 43). Connected bridgeless graphs are 2-edge connected.

connected graph | cyclic edge connectivity | disconnected graph | edge cut | k-edge-connected graph | minimum edge cut | vertex connectivity