{"id":"arxiv/2608.18828","url":"https://arxiv.org/abs/2608.18828","tags":["math.CO"],"score":0,"title":"Counterexample to the Bougard-Joret Conjecture","domain":"math.CO","source":"arxiv","authors":["Joyentanuj Das","Sayan Gupta"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}