Counterexample to the Bougard-Joret Conjecture

Abstract

For admissible integers $n,α,k$, let $f(n,α,k)$ be the minimum number of edges in a $k$-connected graph of order $n$ and independence number $α$. A conjecture of Bougard and Joret predicts that $f(n,α,k)=\lceil nk/2\rceil$ when $n\leq kα$, under the assumptions $n\geq2α$, $n\geqα+k$, $α\geq2$, and $k\geq3$. We disprove this prediction, determine $f(n,α,k)$ throughout the boundary $n=α+k$, and characterize every extremal graph on that boundary. In particular, for every $k\geq4$, \[ 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,α,k)=(7,3,4)$, and no admissible counterexample has smaller order.

Disclosure

“+ k is completely determined by (3.2), and Corollary 3.2 determines every equality case there. Any corrected conjecture must therefore include the exceptional value k 2 − 1 and the extremal family K k−1 ∨ T when α = k − 1. Declaration of generative AI and AI-assisted technologies in the manuscript preparation process During the preparation of this work, the authors used AI to discuss proof strategies, organize and check bibliographic information, check algebraic calculations and proof e”

PDF page 11

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T18:24:48.473491Z

Structural counts