TOPICS
Search

Brandt Conjecture

The Brandt conjecture on the binding number asserts that, for all sufficiently large integers k, every nonempty simple graph G containing no complete graph K_k as a subgraph satisfies

b(G)<=k-2.

Here b(G) is the binding number.

Lin and Yang (2026) proved the bound for every k>=6. It is sharp, since the complete multipartite graph with k-1 equally sized nonempty parts has binding number k-2. The proposed bound fails for k=4, while the paper does not settle k=5. Lin and Yang (2026) report ChatGPT assistance in exploring proof strategies and state that they authored and verified the final proofs.

See also

Binding Number

Explore with Wolfram|Alpha

References

Lin, J. and Yang, H. "A Sharp Bound on the Binding Number of K_k-Free Graphs and the Brandt Conjecture." 20 Oct 2026. https://arxiv.org/abs/2610.28536.

Cite this as:

Weisstein, Eric W. "Brandt Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BrandtConjecture.html

Subject classifications