The first interior shell of the Bougard-Joret extremal problem

Abstract

Let f(n, α, k) be the minimum size of a k-connected graph of order n and independence number α. Das and Gupta recently determined the boundary n = α + k and disproved the proposed Bougard-Joret formula there. We determine the entire admissible first interior shell: f(α + k + 1, α, k) = ⌈k(α + k + 1)/2⌉ for every k ≥ 3 and 2 ≤ α ≤ k + 1. The construction augments classical Harary graphs with complement matchings and attaches an independent set through distinct missing-neighbor pairs. An elementary cyclic-gap proof controls connectivity, including all parity cases. We characterize all extremizers when α = 2 as complements of unions of cycles of lengths at least five, and give the complete nonstar-tree characterization when α = k - 1. The full-shell result is supported by 75 exact finite constructions, an independent re-implementation of the checks, and negative controls. The universal statement follows from the proof, not from finite computation. The general revised first regime and second regime remain unresolved. Source code, data and computational records: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/combinatorics/bougard-joret).