Counterexample to the Bougard-Joret Conjecture

Abstract

For admissible integers $n,\alpha ,k$, let $f(n,\alpha ,k)$ be the minimum number of edges in a $k$-connected graph of order $n$ and independence number $\alpha$. A conjecture of Bougard and Joret predicts that $f(n,\alpha ,k)=\lceil nk/2\rceil$ when $n\le k\alpha$, under the assumptions $n\ge 2\alpha$, $n\ge \alpha +k$, $\alpha \ge 2$, and $k\ge 3$. We disprove this prediction, determine $f(n,\alpha ,k)$ throughout the boundary $n=\alpha +k$, and characterize every extremal graph on that boundary. In particular, for every $k\ge 4$, \[ f(2k-1,k-1,k)=k^2-1, \] whereas the conjectured value is $k^2-\lfloor k/2\rfloor$. The extremal graphs in this family are precisely $\overline K_{k-1}\join T$, where $T$ is an arbitrary tree of order $k$. The smallest-order failure has parameters $(n,\alpha ,k)=(7,3,4)$, and no admissible counterexample has smaller order.

12 pages, 2 figures