On the Connectivity of \((4; g)\)-Cages

Abstract

A \((k;g)\)-graph is a \(k\)-regular graph with girth \(g\). A \((k; g)\)-cage is a \((k; g)\)-graph with the least possible number of vertices. In this paper, we prove that all \((4; g)\)-cages are \(4\)-connected, a special case of the conjecture about \((k; g)\)-cages’ connectivity made by H.L. Fu \(et\; al [1]\).