# Cyclic edge-connectivity of planar graphs (1972)

### SOLVED

**Originator(s):** Michael Plummer, Vanderbilt University

**Conjecture/Question:**
What is the largest cyclic edge-connectivity of a 5-connected planar graph?
The answer is at least 10 and at most 13.

**Definitions/Background/motivation:**
A graph is *cyclically k-edge-connected* if at least *k* edges
must be removed to disconnect it into two components that each contain a cycle.
The cyclic edge-connectivity is the maximum *k* such that the graph is
cyclically *k*-edge-connected. The notion of cyclic edge-connectivity
arose from attempts to prove the Four Color Theorem.

**Comments/Partial results:**
Plummer [P] showed that 4-connected planar graphs can have arbitrarily high
cyclic edge-connectivity; the double wheel
*C*_{m-2}\join 2K_{1} is 4-connected (for *m >= 6*)
and has cyclic edge-connectivity *m*. In the same paper, Plummer showed
that 5-connected planar graphs have cyclic edge-connectivity at most 13 and
exhibited a 5-connected planar graph with cyclic edge-connectivity 10.

**SOLUTION:**
Alfredo Garcia reports that this problem was solved long ago by
Borodin [B1]. He writes: "In that paper the author proved that every plane
graph having minimum degree 5 contains a triangle with weight at most 17. That
immediately implies that the maximum cyclic edge-connectivity of a 5-connected
planar graph is at most 11. Since there are 5-connected plane graphs having
that cyclic edge-connectivity, the maximum cyclic edge-connectivity of a
5-connected plane graph is 11, (also for plane graphs with minimum degree 5).
The same author [commented on] the solution of the conjecture in page 46 of
[B2]."

**References:**

[B1] Borodin, O.V. Solution of Kotzig's and Grünbaum's problems on
separability of a cycle in planar graphs,
Mat. Zametki 46 (1989), 9-12 (in Russian).

[B2] Borodin, O.V. Triangles with restricted degree sum of their boundary
vertices in plane graphs, Discrete Mathematics 137 (1995), 45-51.

[P] Plummer, M.D. On the cyclic connectivity of planar graphs. Graph theory
and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972;
dedicated to the memory of J. W. T. Youngs), pp. 235--242. Lecture Notes in
Math., Vol. 303, Springer, Berlin, 1972.

*
*