HEXAGONbeta

A thrackle on n vertices has fewer than 4n/3 edges

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricscs.DM — Discrete Mathematicscs.CG — Computational Geometry

Contributed by Tejasvi Singh Tomar ↗

Version 1 / Nov 12, 2026 / CC BY 4.0

Abstract

A thrackle is a drawing of a graph in the plane in which every two edges meet exactly once, either at a common endpoint or at a proper crossing. Conway conjectured that a thrackle with nn vertices has at most nn edges. We prove that a thrackle with n≥4n\ge4 vertices has at most 43(n−1)\frac43(n-1) edges, improving the bound 1813(n−1)\frac{18}{13}(n-1) obtained by Tóth and, independently, by Scoppetto. The proof combines Xu's discharging argument with two computer searches, by the method of Fulek and Pach, showing that two generalized dumbbells in the sense of Fulek and Pach are not thrackleable: DB(6,8,−1)\mathrm{DB}(6,8,-1) is a 66-cycle and an 88-cycle sharing one edge; DB(6,10,−3)\mathrm{DB}(6,10,-3) is a 66-cycle and a 1010-cycle sharing a path of three edges. A formal proof in Lean 4 derives the bound from five properties of thrackles and checks the computational facts it uses; Section 6 states what this proof trusts.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.24065370

References

  1. J. M. Boyer and W. J. Myrvold, On the cutting edge: simplified O(n)O(n) planarity by edge addition , J. Graph Algorithms Appl. 8 (2004), 241--273.
  2. U. Brandes, The left-right planarity test , manuscript, 2009.
  3. G. Cairns and Y. Nikolayevsky, Bounds for generalized thrackles , Discrete Comput. Geom. 23 (2000), 191--206.
  4. G. Cairns and Y. Nikolayevsky, Generalized thrackle drawings of non-bipartite graphs , Discrete Comput. Geom. 41 (2009), 119--134.
  5. H. de Fraysseix, P. Ossona de Mendez and P. Rosenstiehl, Trémaux trees and planarity , Internat. J. Found. Comput. Sci. 17 (2006), 1017--1029.
  6. G. Demoucron, Y. Malgrange and R. Pertuiset, Graphes planaires: reconnaissance et construction de représentations planaires topologiques , Rev. Française Recherche Opérationnelle 8 (1964), 33--47.
  7. R. Fulek and J. Pach, A computational approach to Conway's thrackle conjecture , Comput. Geom. 44 (2011), 345--355; arXiv:1002.3904.arXiv
  8. R. Fulek and J. Pach, Thrackles: an improved upper bound , Discrete Appl. Math. 259 (2019), 226--231; we cite the arXiv version, arXiv:1708.08037v1.arXiv
  9. L. Goddyn and Y. Xu, On the bounds of Conway's thrackles , Discrete Comput. Geom. 58 (2017), 410--416.
  10. L. Lovász, J. Pach and M. Szegedy, On Conway's thrackle conjecture , Discrete Comput. Geom. 18 (1997), 369--376.
Show all 14 referencesShow fewer references
  1. T. Scoppetto, Another brick in the wall: a computationally assisted proof of an improved upper bound for thrackles , arXiv:2610.17508v1, 2026.arXiv
  2. M. Tóth, Thrackle drawings of graphs , bachelor thesis, 2026; National Repository of Grey Literature (Prague), record nusl-782605, https://www.nusl.cz/ntk/nusl-782605.link
  3. D. R. Woodall, Thrackles and deadlock , in: Combinatorial Mathematics and its Applications (D. J. A. Welsh, ed.), Academic Press, London, 1971, 335--348.
  4. Y. Xu, A new upper bound for Conway's thrackles , Appl. Math. Comput. 389 (2021), 125573.

Version history

  1. v1 · 12 pagesSubmitted by Tejasvi Singh TomarPublished on Zenodo: https://doi.org/10.5281/zenodo.24065370CurrentNov 12, 2026