This article introduces the minimum spanning $k$-core problem that seeks to find a spanning subgraph with minimum degree at least $k$ (also known as a $k$-core) that minimizes the total cost of the edges in the subgraph. The concept of $k$-cores was introduced in social network analysis to identify denser portions of a social network. We exploit the graph-theoretic properties of this model to introduce a new approach to survivable inter-hub network design via spanning $k$-cores that preserves connectivity and diameter under limited edge failures. The deterministic version of the problem is polynomial-time solvable due to its equivalence to generalized graph matching. We propose two conditional value-at-risk (CVaR) constrained optimization models to obtain risk-averse solutions for the minimum spanning $k$-core problem under probabilistic edge failures. We present polyhedral reformulations of the convex piecewise linear loss functions used in these models that enable Benders-like decomposition approaches. A decomposition and branch-and-cut approach is then developed to solve the scenario-based approximation of the CVaR-constrained minimum spanning $k$-core problem for the aforementioned loss functions. The computational performance of the algorithm is investigated via numerical experiments.