Reduction for 3-Connected Graphs of Minimum
Degree at Least Four

Sheng Bau 1 and Akira Saito 2
1 College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350002, P. R. China
2 Department of Computer Science, Nihon University, Tokyo 156-8550, Japan

Abstract     Full Text  PDF

A reduction theorem is obtained for the class of $3$-connected graphs of minimum degree at least four using three basic operations: contraction of an edge, splitting and crown reduction. We prove that if a vertex $x$ in a 3-connected graph of order at least six and minimum degree at least four is specified, then we can always find one of the following in the proximity of $x$: (1) an edge whose contraction results in a 3-connected graph of minimum degree at least four, (2) a vertex of degree four at which some splitting produces a 3-connected graph of minimum degree at least four, (3) a crown whose reduction gives a 3-connected graph of minimum degree at least four.