When embedding a graph we require that edges do not cross. What about the opposite extreme, where there are lots of edge crossings? As usual, in a drawing of a graph G in the plane two edges may share a single common point provided that they are nonadjacent and cross at that point.

A thrackle is a drawing of a graph such that every pair of nonadjacent edges cross. The name is coined by John Conway, who notes that a thrackle is also a tangle of fishing line. The name is appropriate, as a thrackled drawing of a graph appears very tangled indeed.

Conjecture: If a graph can be thrackled, then its number of edges is not greater than its number of vertices.

The converse is not true as shown by a 4-cycle.

Woodall [W] has shown that every cycle of length at least 5 can be thrackled and that every tree can be thrackled. In fact, the thrackle conjecture reduces to showing that the one-point union of two even-length cycles cannot be thrackled.

The best positive result I know of is due to Mario Szegedy (personal communication) who showed that if a graph can be thrackeled, then the number of edges is at most $2|V|-3$.

I believe that John Conway is offering a prize of $1000 for a solution to this conjecture.

[W] D.R.\ Woodall, Thrackles and deadlock, in: Combinatorial

held at the Mathematical Institute (D.A.J. Welsh, Ed.) Oxford

(1969) 335-348.

Submitted by: (With thanks to John Conway) by : Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.