Conway's Thrackle Conjecture - Thrackle Conjecture

Thrackle Conjecture

John H. Conway has conjectured that, in any thrackle, the number of edges is at most equal to the number of vertices. Conway himself uses the terminology paths and spots (for edges and vertices respectively), so Conway's thrackle conjecture was originally stated in the form every thrackle has at least as many spots as paths.

Equivalently, the thrackle conjecture may be stated as every thrackle is a pseudoforest. More specifically, if the thrackle conjecture is true, the thrackles may be exactly characterized by a result of Woodall: they are the pseudoforests in which there is no cycle of length four and at most one odd cycle.

It has been proven that every cycle graph other than C₄ has a thrackle embedding, which shows that the conjecture is sharp. That is, there are thrackles having the same number of spots as paths. At the other extreme, the worst case scenario is that the number of spots is twice the number of paths; this is also attainable.

The thrackle conjecture is known to be true for thrackles drawn in such a way that every edge is an x-monotone curve, crossed at most once by every vertical line.