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 Cm-2\join 2K1 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.

Back to Index Page Link to Glossary