Open AccessContractible Edges and Peripheral Cycles in 3-Connected Graphs
Author(s) -
Alexander Slodkowski,
Timothy Huber
Publication year - 2021
Publication title -
journal of student research
Language(s) - English
Resource type - Journals
ISSN - 2167-1907
DOI - 10.47611/jsr.v10i2.1193
Subject(s) - combinatorics , contractible space , mathematics , lemma (botany) , discrete mathematics , pathwidth , graph , line graph , ecology , poaceae , biology
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.