Conway thrackle constant

Description of constant

In topological graph theory, a thrackle is a drawing of a finite graph in the plane in which every pair of edges meets precisely once, either at a common endpoint or at a proper crossing. If $t(n)$ denotes the maximum number of edges in a thrackle on $n$ vertices, then Conway's thrackle conjecture states that $t(n)=n$ for every $n\ge 3$. <a href="#FP2011-def-tn-conj">[FP2011-def-tn-conj]</a>

For a finite graph $G$, write $V(G)$ for its vertex set and $E(G)$ for its edge set. We define

$$C_{78}:=\sup \left\{\frac{|E(G)|}{|V(G)|}:G\text{ admits a thrackle drawing in the plane}\right\}.$$

Equivalently,

$$C_{78}=\underset{n\ge 1}{\sup }\frac{t(n)}{n}.$$

Thus Conway's thrackle conjecture is equivalent to the assertion that $C_{78}=1$. <a href="#FP2011-def-tn-conj">[FP2011-def-tn-conj]</a>

At present, the best established range is

$$1\le C_{78}\le \mathrm{1.393.}$$

The lower bound comes from thrackled cycles, and the upper bound from Xu's current record bound $m\le 1.393(n-1)$ as recorded in recent survey-style sources. <a href="#FP2011-open-sharp">[FP2011-open-sharp]</a> <a href="#KSTZ2025-current-best-special">[KSTZ2025-current-best-special]</a>

Known upper bounds

Known lower bounds

Additional comments and links

• 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$. <a href="#FP2011-def-tn-conj">[FP2011-def-tn-conj]</a> <a href="#FP2011-open-sharp">[FP2011-open-sharp]</a>

• Solved subclasses. The conjecture is known for geometric (straight-line) thrackles, outerplanar thrackles, and $x$-monotone thrackles. <a href="#KSTZ2025-current-best-special">[KSTZ2025-current-best-special]</a>

• Wikipedia page on thrackles

References

• <a id="CN2000"></a>[CN2000] Cairns, Grant; Nikolayevsky, Yury. Bounds for generalized thrackles. Discrete & Computational Geometry 23 (2000), no. 2, 191–206. DOI: 10.1007/PL00009495. Google Scholar
• <a id="CN2000-ub-lps-cn"></a>[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$.”

• <a id="FP2011"></a>[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
• <a id="FP2011-def-tn-conj"></a>[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 $\epsilon >0$, we give an algorithm terminating in $e^{O((1/{\epsilon }^2)\ln (1/\epsilon ))}$ steps to decide whether $t(n)\le (1+\epsilon )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$.”
• <a id="FP2011-open-sharp"></a>[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].”

• <a id="FP2019"></a>[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
• <a id="FP2019-ub-gx-fp"></a>[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.”

• <a id="KSTZ2025"></a>[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
• <a id="KSTZ2025-current-best-special"></a>[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].”

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.