The Exact Degree Threshold for Complement Connectivity

For a graph $G$, we investigate sufficient degree conditions under which either $G$ or its complement $\bar{G}$ is $k$-connected. Motivated by a theorem of Hellwig and Volkmann, we introduce the notion of complement connectivity admissible pairs and define the parameter $\mathcal{C}(k)$ as the minimum degree threshold guaranteeing that either $G$ or $\bar{G}$ is $k$-connected whenever $\delta (G)\ge \mathcal{C}(k)$ and $\mathrm{\Delta }(G)\le \mathrm{\mid }V(G)\mathrm{\mid }-1-\mathcal{C}(k)$. We prove that $\mathcal{C}(k)=2k-2$ for every $k\ge 2$, thereby determining the exact degree threshold. As an application, we derive a Nordhaus–Gaddum type product condition, showing that for $n\ge 4k-5$, the condition $\delta (G)\delta (\bar{G})\ge (2k-3)(n-2k+2)$ guarantees that either $G$ or $\bar{G}$ is $k$-connected. Finally, we show that no analogous product condition depending only on $k$ can exist.