**Originator(s):**
H. L. Fu, K. C. Huang, and C. A. Rodger (Auburn Univ.)

**Definitions:**
A (*k,g*)-*cage* is a graph with minimum number of vertices
among the *k*-regular graphs with girth *g*.
Erdos and Sachs [ES] showed the existence of cages for *k,g\ge2*.

**Conjecture/Question:**
Every (*k,g*)-cage is *k*-connected.

**Comments/Partial results:**
Fu-Huang-Rodger [FHR] proved the conjecture for *k=3*.
Jiang-Mubayi [JM] and Daven-Rodger [DR] independently proved
that all cages with *k\ge3* are 3-connected.
Pelayo-Marcote-Balbuena [PMB] showed that 3-regular cages
with girth at least 5 are quasi-4-connected.

In the study of connectivity, a graph is said to be
*maximally connected* if its connectivity equals its minimum degree.
It is *superconnected* if it is maximally connected and every
minimum cutset is trivial (a vertex neighborhood). A 3-regular graph is
*quasi-4-connected* if it is superconnected and deletion of any
minimum cutset leaves only two components.

**References:**
[DR] M. Daven and C.A. Rodger, (k, g)-cages are 3- connected,
Discrete Math. 199 (1999), 207–215.

[ES] P. Erdos and H. Sachs, Regulare Graphen gegebener Taillen-
weite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math.
Nat.) 12 (1963), 251–257.

[FHR] H.L. Fu, K.C. Huang and C.A. Rodger, Connectivity of Cages,
J. Graph Theory 24 (1997), 187–191.

[JM] T. Jiang and D. Mubayi, Connectivity and Separating Sets of
Cages, J. Graph Theory 29 (1998), 35–44.

[PMB] I. Pelayo, X. Marcote, and C. Balbuena,
Every cubic cage is quasi-4-connected.

Posted 06/12/05; Last update 06/12/05