Let
be an edge cut of a connected
graph .
Then the cyclic edge connectivity is the size of a smallest cyclic edge cut, i.e.,
a smallest edge cut such that has two connected components, each of which contains at
least one graph cycle. Cyclic edge connectivity was
considered as early as 1880 by Tait (1880).

Note that Grünbaum (2003, p. 365) and others use the term "cyclically -connected"
(omitting in the word "edge") to refer to a graph that cannot be broken
into two separate parts each of which contain a cycle by an edge
cut of fewer than edges.

A cyclic edge cut does not exist for all graphs. For example, a graph containing fewer than two cycles cannot have two components each of which contain a cycle. Examples
of graphs having no cyclic edge cuts include the complete
graphs
and ,
the utility graph , and the wheel graphs
(Dvorák et al. 2004). A graph for which no cyclic edge cut exists may
be taken to have (Lou et al. 2001).

The cyclic edge connectivity of the Petersen graph is
(Holton and Sheehan 1993, p. 86; Lou et al. 2001). This can be seen from
the fact that removing the five "radial" edges leaves a disconnected inner
pentagrammic cycle and outer pentagonal cycle.

Cyclic edge connectivity is most commonly encountered in the definition of snark graphs, which are defined as cubic cyclically 4-edge-connected
graphs of girth at least 5 having edge
chromatic number 4.

Birkhoff (1913) reduced the four-color problem to cyclically 5-edge-connected polyhedral graphs (Grünbaum 2003, p. 365). Hunter (1962) conjectured that such graphs
are all Hamiltonian, but this was refuted with
the discovery of the 162-vertex cubic nonhamiltonian
162-vertex Walther graph (Walther 1965, Grünbaum
2003, p. 365).

Plummer (1972) showed that a planar 5-connected graph has a cyclic edge connectivity of at most 13, while a planar 4-connected graph may have cyclic edge connectivity of any integer value 4 or larger. Borodin (1989) showed that the maximum cyclic edge connectivity of a 5-connected planar graph is at most 11.

The cyclic edge connectivity of a simple graph on nodes satisfies

with equality for the complete graph when ,
i.e.,
for
(Lou et al. 2001).

Birkhoff, G. D. "The Reducibility of Maps." Amer. J. Math35, 115-128, 1913.Borodin, O. V. "Solution
of Kotzig's and Grünbaum's Problems on Separability of a Cycle in Planar Graphs."
Mat. Zametki46, 9-12, 1989.Dvorák, Z.; Kára,
J.; Král', D.; and Pangrác, O. "An Algorithm for Cyclic Edge Connectivity
of Cubic Graphs." In Algorithm Theory--SWAT 2004 (Ed. T. Hagerup
and J. Katajainen). Berlin: Springer, pp. 236-247, 2004.Grünbaum,
B. Convex
Polytopes, 2nd ed. New York: Springer-Verlag, 2003.Holton, D. A.
and Sheehan, J. The
Petersen Graph. Cambridge, England: Cambridge University Press, p. 86,
1993.Hunter, H. F. On Non-Hamiltonian Maps and their Duals.
Ph. D. thesis. Troy, NY: Rensselaer Polytechnic Institute, 1962.Lou,
D.; Teng, L.; and Wu, S. "A Polynomial Algorithm for Cyclic Edge Connectivity
of Cubic Graphs." Austral. J. Combin.24, 247-259, 2001.Plummer,
M. D. "On the Cyclic Connectivity of Planar Graphs." In Graph Theory
and Applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972).
Berlin: Springer-Verlag, pp. 235-242, 1972.Tait, P. G. "Remarks
on the Colouring of Maps." Proc. Roy. Soc. Edingburg10, 501-503,
1880.Walther, H. "Ein kubischer, planarer, zyklisch fünffach
zusammenhängender Graf, der keinen Hamiltonkreis besizt." Wiss. Z. Hochschule
Elektrotech. Ilmenau11, 163-166, 1965.