TOPICS
Search

Edge Connectivity


The edge connectivity, also called the line connectivity, of a graph is the minimum number of edges lambda(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 kappa(G) be the vertex connectivity of a graph G and delta(G) its minimum degree, then for any graph,

 kappa(G)<=lambda(G)<=delta(G)

(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"].


See also

Connected Graph, Cyclic Edge Connectivity, Disconnected Graph, Edge Cut, k-Edge-Connected Graph, Minimum Edge Cut, Vertex Connectivity

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 43, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 177-178, 1990.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Edge Connectivity

Cite this as:

Weisstein, Eric W. "Edge Connectivity." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EdgeConnectivity.html

Subject classifications