Conway's Thrackle Conjecture

Conway’s Thrackle Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A thrackle is a plane drawing of a finite simple graph in which every pair of distinct edges meets exactly once, either at a common endpoint or at a proper interior crossing. The usual drawing conventions exclude overlapping edge segments, tangencies and a vertex in the interior of another edge. The conjecture is $|E(G)|\leq|V(G)|$. [S1] [S2]

Statement recorded in the supplied source.

Does every thrackle have at most as many edges as vertices? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove or disprove m<=n for every planar thrackle. [S1]

Short English statement

If every pair of drawn edges meets exactly once, can the graph ever have more edges than vertices?

Research attempt

Status: UNRESOLVED. We give exact crossing accounting, a parity obstruction to two vertex-disjoint odd cycles, and prove the desired edge bound for pseudoforests. The missing step is ruling out more complicated cycle structure under the geometric thrackle condition.

Source check and planar scope.

Hernández-Vélez--Kynčl--Salazar [S2], consulted 1 October 2026, studies thrackles on nonplanar surfaces and explicitly distinguishes them from Conway's planar conjecture. Its nonplanar counterexamples do not refute the target here. We use only the plane. The combinatorial calculations below assume the usual general-position drawing conventions in the definition; multiple crossings can be separated locally without changing which pairs of independent edges cross.

Counting crossings from the degree sequence.

Let the graph have $n$ vertices, $m$ edges, and vertex degrees $d_v$. Two adjacent edges meet at their common endpoint and therefore cannot cross in their interiors. Every independent pair of edges crosses once. In a simple graph two distinct edges share at most one endpoint, so the total number $c$ of interior pairwise crossings is exactly \[ c=\binom m2-\sum_v\binom{d_v}{2}. \] This is a necessary numerical identity for a thrackle drawing. It does not assert that every graph with a nonnegative right side admits such a drawing; nonnegativity alone merely counts its independent pairs.

Replacing every crossing by a new degree-four vertex produces a plane graph with $n+c$ vertices and $m+2c$ edges: a crossing splits each of its two participating edges into one additional segment. A coarse planar edge bound, when applicable after simplifying degeneracies, still contains $c$ on the upper side. Substituting the displayed formula can introduce terms quadratic in $m$. Thus ordinary Euler counting does not directly yield the desired linear inequality $m\le n$; treating crossing vertices as though they were original graph vertices loses essential information.

A planar parity obstruction.

Two closed polygonal curves in the plane in transverse general position have an even number of intersections, counted modulo two. One way to see this is to define the mod-two winding number of one curve on the complementary regions. It is zero in the unbounded region and changes across each curve arc. Traversing the other closed curve returns to the starting region, so the total number of changes is even. Self-intersections of either curve do not invalidate this mod-two argument; a small local subdivision handles them.

Now suppose a thrackle graph contains vertex-disjoint cycles $C$ and $D$ of lengths $a$ and $b$. Every edge of $C$ is independent of every edge of $D$, and hence crosses it exactly once. The associated closed curves therefore have exactly $ab$ mutual crossings, counted by pairs of edges. Parity forces $ab$ to be even. In particular, two vertex-disjoint odd cycles cannot occur in a planar thrackle.

The vertex-disjoint qualification is indispensable. If the cycles meet at a graph vertex, the traversal includes endpoint contacts rather than only transverse interior crossings. Counting those as ordinary crossings would require an additional local analysis that has not been given here.

A class where the edge target is proved.

A pseudoforest is a graph each of whose components has at most one cycle. A connected acyclic component on $v$ vertices has $v-1$ edges, by deleting leaves inductively. A connected component with exactly one cycle has $v$ edges: remove one cycle edge to obtain a tree. Summing over components gives $m\le n$ for every pseudoforest, whether or not it admits a thrackle drawing.

Consequently any counterexample thrackle would contain a connected component with at least two independent cycles in the cycle-space sense, namely $m_C-v_C+1\ge2$. The parity obstruction excludes the subcase of two vertex-disjoint odd cycles. It does not exclude cycles sharing vertices or edges, nor does it prove here that every cycle in a thrackle has odd length. Filling those gaps by assertion would be circular.

Sharp examples and a failed enlargement.

A triangle drawn with straight edges is a thrackle with three vertices and three edges: all pairs meet at one common endpoint. A star is a thrackle with $m=n-1$, since its distinct straight radial edges meet only at the centre. Disjointly placing two triangles is not a thrackle, because their independent edges fail to meet. Trying to route their edges so that every cross-pair meets exactly once also fails by the odd-cycle parity argument: it would create nine transverse crossings between two closed curves.

These checks show why taking disjoint unions of individually valid drawings is not a legitimate construction rule. The thrackle condition is global over every pair of edges, including pairs belonging to different components.

Final gap and verification limits.

The degree identity and cycle parity are exact mathematical checks; no graph-drawing search was run. A candidate drawing would have to certify every independent pair's unique crossing and every adjacent pair's absence of an interior crossing. A sketch with visually close strands is not such a certificate.

The unresolved step is proving that no admissible multi-cycle component can force total edge excess, or constructing one with fully checked geometry. The current argument isolates some forbidden cycle arrangements but leaves other arrangements untouched. It therefore remains an unresolved attempt on the original planar conjecture, not a consequence of the cited nonplanar results.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1403 (GRAPH-016), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 C. Hernández-Vélez, J. Kynčl and G. Salazar, Thrackles on nonplanar surfaces, arXiv:2506.11808 $2025$. https://arxiv.org/abs/2506.11808. Bibliographic information from the supplied record.

• S3 TOPP Problem 30: Thrackles. https://topp.openproblem.net/p30. Bibliographic information from the supplied record.