For integers n,alpha,k satisfying n≤ k alpha, n≥ 2 alpha, n≥ alpha+k, alpha≥ 2, and k≥ 3, define f(n,alpha,k) to be the minimum of |E(G)| over all k-connected graphs G with |V(G)|=n and independence number alpha(G)=alpha. The Bougard–Joret Conjecture asserts that f(n,alpha,k)=lceil fracnk2rceil.

Bougard–Joret conjecture

Bougard and Joret conjectured a formula for the minimum size $f(n,\alpha,k)$ of a $k$ -connected graph with order $n$ and independence number $\alpha$ . Their general conjecture was proposed after settling the connected and $2$ -connected cases.

Known results

The connected and $2$ -connected cases were settled by Bougard and Joret.
They proved structural refinements of Brouwer’s theorem.
The conjectured value was verified for $\alpha=2$ and $n\ge 2k$ .

August 2026 boundary refutation

A new paper determines the extremal function on the boundary $n=\alpha+k$ and gives the smallest-order failure at $(n,\alpha,k)=(7,3,4)$ . It also supplies an explicit infinite family showing that the conjectured formula fails for every $k\ge 4$ .

Current status (as of August 2026): The conjecture is false on the boundary $n=\alpha+k$ for every $k\ge 4$ , with smallest failure $(7,3,4)$ , while the full extremal function in all parameters remains open.

Bougard–Joret conjecture

Progress summary

Primary source

Additional references

Solutions 0