Barát–Thomassen conjecture

Status solved high confidence

The Barát–Thomassen conjecture was proved in full by Bensmail, Harutyunyan, Le, Merker, and Thomassé (2017). They showed that for every tree T on m edges there exists a constant k_T such that every k_T-edge-connected graph whose number of edges is divisible by m can be edge-decomposed into copies of T, confirming exactly the statement as given. The paper appeared in Journal of Combinatorial Theory, Series B, volume 124 (2017), following an arXiv preprint from March 2016.

Cited literature (2)

• proof A Proof of the Barát–Thomassen Conjecture (2017)
  Bensmail, J., Harutyunyan, A., Le, T.-N., Merker, M., Thomassé, S. · Journal of Combinatorial Theory, Series B · arXiv:1603.00197 · doi:10.1016/j.jctb.2016.12.006

  Proves the full conjecture: for every tree T on m edges there exists k_T such that every k_T-edge-connected graph with size divisible by m admits an edge-decomposition into copies of T.

• partial Edge-partitioning a graph into paths: beyond the Barát–Thomassen conjecture (2015)
  Bensmail, J., Harutyunyan, A., Le, T.-N., Thomassé, S. · arXiv preprint · arXiv:1507.08208

  Proves the path case with improved edge-connectivity bounds and proposes a refinement of the conjecture; precursor to the full proof.

Reviewer notes. The conjecture is fully resolved. The proof (arXiv:1603.00197, JCTB 124, 2017) directly matches the statement as given in Bondy–Murty: for every tree T there exists k(T) such that every simple k(T)-edge-connected graph with |E(G)| divisible by e(T) decomposes into copies of T. The DOI 10.1016/j.jctb.2016.12.006 is taken from the book's editorial note; the redirect to linkinghub.elsevier.com/pii/S0095895616301137 was confirmed but content not retrieved. The related corpus record arXiv:1507.08208 (Bensmail–Harutyunyan–Le–Thomassé, 2015) handled only the path case and proposed a refinement of the conjecture; it is strictly weaker than the settled full result.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).