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.

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.

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

There have been some questions concerning the origin of the word thrackle. Conway says "When I was a teenager, on holiday with my parents in Scotland, we once stopped to ask directions of a man who was fishing by the side of a lake. He happened to mention that his line was thrackled. I'd previously called this kind of drawing a tangle, but since I'd just found a knot-theoretical use for that term, I changed this to thrackle. Several people have told me that they've searched in vain for this word in dialect dictionaries, but since I quizzed the fisherman about it, I'm sure I didn't mishear it; he really did use it." (Thanks to Jacob E. Goodman for digging up this quote from Conway.) The name is indeed appropriate, as a drawing with the maximum number of crossings indeed resembles a highly-knotted fishing line.

[W] D.R. Woodall, Thrackles and deadlock, in: Combinatorial Mathematics and its Applications, Proceedings of a Conference held at the Mathematical Institute (D.A.J. Welsh, Ed.) Oxford (1969) 335-348.

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

Send comments to dan.archdeacon@uvm.edu

August, 1995 (Last edited Feb, 2001)