Covering contractible edges in 3‐connected graphs. I: Covers of size three are cutsets
Akira Saito · Journal of Graph Theory · 1990
Abstract An edge of a 3‐connected graph is said to be contractible if its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (Scientia (A) 2 (1988) 101–105) that the set of contractible edges in a 3‐connected graph cannot be covered by two vertices, and extended this result to a three‐vertex covering. We also study the existence of a contractible edge whose contraction preserves a specified cycle, and show that a non‐hamiltonian 3‐connected graph has a contractible edge whose contraction preserves the circumference.