A graph is -edge-connected
if there does not exist a set of edges whose removal disconnects the graph (Skiena 1990,
p. 177). 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.

-edge-connectedness
graph checking is implemented in the Wolfram
Language as KEdgeConnectedGraphQ [g ,
k ].

The following table gives the numbers of -edge-connected graphs for -node graphs.

OEIS , 2, ...0 A000719 0,
1, 2, 5, 13, 44, 191, ... 1 A052446 0, 1, 1, 3, 10, 52,
351, ... 2 A052447 0, 0, 1, 2, 8, 41, 352, ... 3 A052448 0,
0, 0, 1, 2, 15, 121, ... 4 0, 0, 0, 0, 1, 3, 25, ... 5 0, 0, 0, 0, 0, 1, 3, ... 6 0, 0, 0, 0, 0, 0, 1, ...

See also Cyclic Edge Connectivity ,

Edge Connectivity ,

Edge
Cut ,

Graph Bridge ,

k -Connected
Graph
Explore with Wolfram|Alpha
References Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 45, 1994. Skiena,
S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990. Sloane, N. J. A. Sequences A000719 /M1452,
A052446 , A052447 ,
and A052448 in "The On-Line Encyclopedia
of Integer Sequences." Referenced on Wolfram|Alpha k-Edge-Connected Graph
Cite this as:
Weisstein, Eric W. "k-Edge-Connected Graph."
From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/k-Edge-ConnectedGraph.html

Subject classifications