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. 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
Mathematics and its Applications, Proceedings of a Conference
held at the Mathematical Institute (D.A.J. Welsh, Ed.) Oxford
Submitted by: (With thanks to John Conway) by : Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.
Send comments to email@example.com