Contractible Edges and Peripheral Cycles in 3-Connected Graphs
Keywords:contractible edges, induced subgraphs, non-separating cycles, peripheral cycles, 3-connected graphs
Peripheral cycles (induced non-separating cycles) in a general 3-connected graph are analogous to the faces of a polyhedron. Using the works of various authors, this paper explores the distribution of contractible edges in 3-connected graphs as needed to prove a major result originally by Tutte: each edge in a 3-connected graph is part of at least 2 peripheral cycles that share only the edge and its end vertices. A complete, alternative proof of this theorem is provided. The inductive step is generalized into a new independent lemma, which states that each edge in a 3-connected graph with a non-adjacent contractible edge has at least as many peripheral cycles as in the contracted one.
References or Bibliography
K. Ando, H. Enomoto, and A. Saito, Contractible edges in 3-connected graphs. J. Combin. Theory Ser. B 42 (1987), 87-93.
R. Diestel, Graph Theory. Springer, NY (2005).
R. Halin, Zur Theorie der n-fach zusammenhängenden Graphen, Abh. Math. Sem. Univ. Hamburg 33 (1969), 133-164.
A. Kelmans, A new planarity criterion for 3-connected graphs, J. Graph Theory 5 (1981), 259-267.
K. Ota and A. Saito, Non-separating induced cycles in 3-connected graphs. Scientia Ser. A 2 (1988) 101-105.
A. Saito, Covering contractible edges in 3-connected graphs; I: covers of size three are cutsets. J. Graph Theory 14 (1990), 635-643.
R. Thomas, Lecture 7. Web. https://people.math.gatech.edu/~thomas/TEACH/6014/lecture7.pdf
C. Thomassen, Planarity and duality of finite and infinite graphs, J. Combin. Theory Ser. B 29 (1980), 244-271.
W. T. Tutte, A theory of 3-connected graphs. Nederl. Akad. Wetensch. Proc. Ser. A 64 (1961) 441-455.
W. T. Tutte, How to draw a graph. Proc. London Math. Soc. (3) 13 (1963) 743-68.
How to Cite
Copyright (c) 2021 Alexander Slodkowski; Dr. Timothy Huber
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright holder(s) granted JSR a perpetual, non-exclusive license to distriute & display this article.