The Thrackle Conjecture

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.

References:

[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)