The Vertices of Lower Degree in Contraction-Critical \(\kappa\) Connected Graphs

Abstract

Let \(G\) be a \(contraction-critical\) \(\kappa\)-connected graph. It is known (see Graphs and Combinatorics, \(7 (1991) 15-21\)) that the minimum degree of \(G\) is at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\). In this paper, we show that if \(G\) has at most one vertex of degree \(\kappa\), then either \(G\) has a pair of adjacent vertices such that each of them has degree at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\), or there is a vertex of degree \(\kappa\) whose neighborhood has a vertex of degree at most \(\lfloor \frac{4\kappa}{4} \rfloor – 1\). Moreover, if the minimum degree of \(G\) equals to \(\frac{5\kappa}{4} – 1\) (and thus \(\kappa = 0 \mod 4\)), Su showed that \(G\) has \(\kappa\) vertices of degree \(\frac{5\kappa}{4} – 1\), guessed that \(G\) has \(\frac{3\kappa}{2}\) such vertices (see Combinatorics Graph Theory Algorithms and Application (Yousef Alavi et. al Eds.),World Scientific, \(1993, 329-337\)). Here, we verify that this is true.