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