Conway thrackle constant ($C_{78}$)

• Conjectural value. Conway's conjecture predicts that $C_{78}=1$. This would be best possible, because cycles of length at least five already attain edge-vertex ratio $1$. [FP2011-def-tn-conj] [FP2011-open-sharp]

• Solved subclasses. The conjecture is known for geometric (straight-line) thrackles, outerplanar thrackles, and $x$-monotone thrackles. [KSTZ2025-current-best-special]

• Wikipedia page on thrackles

References (from the repository page)

• [CN2000] Cairns, Grant; Nikolayevsky, Yury. Bounds for generalized thrackles. Discrete & Computational Geometry 23 (2000), no. 2, 191–206. DOI: 10.1007/PL00009495. Google Scholar

• [CN2000-ub-lps-cn] loc: Springer PDF p.1, Introduction, file: 10.1007-PL00009495.pdf quote: “Lovász et al. proved: Theorem 1 [LPS]. (a) for thrackles, $m \le 2n - 3$, (b) for generalized thrackles, $m \le 3n - 4$, (c) a bipartite graph can be drawn as a generalized thrackle if and only if it is planar. We give the following improvement: Theorem 2. (a) for thrackles, $m \le \frac{3}{2}(n - 1)$, (b) for generalized thrackles, $m \le 2n - 2$.”

• [FP2011] Fulek, Radoslav; Pach, János. A computational approach to Conway's thrackle conjecture. Computational Geometry 44 (2011), no. 6–7, 345–355. DOI: 10.1016/j.comgeo.2011.02.001. arXiv PDF: arXiv:1002.3904. Google Scholar

• [FP2011-def-tn-conj] loc: arXiv PDF p.1, Abstract, file: 1002.3904.pdf quote: “A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let $t(n)$ denote the maximum number of edges that a thrackle of $n$ vertices can have. According to a 40 years old conjecture of Conway, $t(n) = n$ for every $n \ge 3$. For any $\varepsilon > 0$, we give an algorithm terminating in $e^{O((1/\varepsilon^2)\ln(1/\varepsilon))}$ steps to decide whether $t(n) \le (1 + \varepsilon)n$ for all $n \ge 3$. Using this approach, we improve the best known upper bound, $t(n) \le \frac{3}{2}(n - 1)$, due to Cairns and Nikolayevsky, to $\frac{167}{117}n < 1.428n$.”

• [FP2011-open-sharp] loc: arXiv PDF p.1, §1 Introduction, file: 1002.3904.pdf quote: “A drawing of $G$ is called a thrackle if every pair of edges meet precisely once, either at a common vertex or at a proper crossing. (A crossing $p$ of two curves is proper if at $p$ one curve passes from one side of the other curve to its other side.) More than forty years ago Conway [18, 2, 15] conjectured that every thrackle has at most as many edges as vertices, and offered a bottle of beer for a solution. Since then the prize went up to a thousand dollars. In spite of considerable efforts, Conway’s thrackle conjecture is still open. It is believed to represent the tip of an “iceberg,” obstructing our understanding of crossing patterns of edges in topological graphs. If true, Conway’s conjecture would be tight as any cycle of length at least five can be drawn as a thrackle, see [17].”

• [FP2019] Fulek, Radoslav; Pach, János. Thrackles: An improved upper bound. Discrete Applied Mathematics 259 (2019), 226–231. DOI: 10.1016/j.dam.2018.12.025. arXiv PDF: arXiv:1708.08037. Google Scholar

• [FP2019-ub-gx-fp] loc: arXiv PDF p.1, §1 Introduction, file: 1708.08037v1.pdf quote: “The first linear upper bound on the number of edges of a thrackle, in terms of the number of vertices $n$, was established in [6 ]. This bound was subsequently improved in [ 1] and [4 ], with the present record, $1.4n$, held by Goddyn and Xu [ 5], which also appeared in the master thesis of the second author [9]. One of the aims of this note is to show that this latter bound is not best possible. Theorem 1. Any thrackle on $n > 3$ vertices has at most $1.3984n$ edges.”

• [KSTZ2025] Keszegh, Balázs; Suk, Andrew; Tardos, Gábor; Zeng, Ji. Unavoidable patterns and plane paths in dense topological graphs. Preprint (2025). arXiv:2512.04795. arXiv PDF: arXiv:2512.04795. Google Scholar

• [KSTZ2025-current-best-special] loc: arXiv PDF p.1, §1 Introduction, file: 2512.04795.pdf quote: “The famous thrackle conjecture of Conway states that a thrackle with $n$ vertices has at most $n$ edges, see [21] for a detailed history of the problem. For the special case of geometric graphs, the thrackle conjecture is proved by Erdős, and later, a short proof is given by Perles (see [21]). The proof of Perles also works if the drawing is outerplanar [7], i.e., if the points lie on the boundary of a disk and the edges lie inside this disk. The case that the edges are $x$-monotone is settled by Pach and Sterling [21]. In general, after a long series of improvements (Lovász–Pach–Szegedy [17] proved $2n$, Cairns–Nikolayevsky [6] proved $1.5n$, improved further by Fulek–Pach [12, 13] and Goddyn–Xu [14]), the current best upper bound on the number of edges of an $n$-vertex thrackle is $1.393(n - 1)$ by Xu [31].”

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 1; best known upper bound 1.393. Values marked with an asterisk have minimal verification.

Known upper bounds

Known lower bounds