k-Edge-Connected Graph

A -edge-connected graph is a graph on at least two vertices that remains connected after deletion of any set of fewer than graph edges, where is a positive integer (Skiena 1990, p. 177). Equivalently, its edge connectivity satisfies . The edge connectivity is at most the smallest vertex degree, since deleting all graph edges incident to a minimum-degree vertex disconnects the graph. Complete bipartite graphs attain this bound.

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

The following table gives the numbers of unlabeled simple graphs on nodes having edge connectivity exactly , rather than at least . The row counts disconnected graphs, excluding the singleton graph.

	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, ...