A Sharp Lower Bound for the Number of Connectivity-Redundant Nodes

We call a node of a simple graph \({connectivity\;-redundant}\) if its removal does not diminish the connectivity. Studying the distribution of such nodes in a CKL-graph, i.e., a connected graph \(G\) of order \(\geq 3\) whose connectivity \(\kappa\) and minimum degree \(\delta\) satisfy the inequality \(\kappa \geq (\frac{3\kappa – 1}{2})\), we obtain a best lower bound, sharp for any \(\kappa > 1\), for the number of connectivity-redundant nodes in \(G\), which is \(\kappa + 1\) or \(\kappa + 2\) according to whether \(\kappa\) is odd or even, respectively. As a by-product we obtain a new proof of an old theorem of Watkins concerning node-transitive graphs.