Critically \((k,k)\)-connected graphs (Q1093652)

A graph G, with vertex connectivity \(\kappa(G)\), minimum degree \(\delta(G)\), and complement \(\bar G,\) is critically \((k,k)\)-connected if \(\kappa(G)=\kappa(\bar G)=k\), and for each vertex v of G, either \(\kappa(G-v)=k-1\) or \(\kappa(\bar G-v)=k-1\). Theorem: If G is a critically \((k,k)\)-connected graph with \(k\geq 2\), \(\delta(G)\geq (3k-1)\), and \(\delta(\bar G)\geq (3k-1)\), then 3k\(\leq | V(G)| \leq 4k\). Moreover, it is also shown that the upper bound is sharp for \(k\geq 3\).