Stephan Wehner

First up: May 7, 1996.

Major update: March 23, 2000

Adding sequence types for 11-cycle: March 7, 2010

Last update: March 7, 2010

thrackle.org home

In the late sixties, John Conway posed the following problem:

A thrackle embedding of a graph is a function which maps each vertex to a point and each edge to a closed continuous lines in the plane such that

- No line crosses itself.
- Each two lines intersect exactly once.
- If two vertices are connected by an edge, then the two vertices are mapped to the two endpoints of the image of the edge.
- If two lines intersect, then either in a common endpoint, or the two lines cross over at the intersection.

Is there a graph which has more edges than vertices and has a thrackle embedding?

Conway's thrackle conjecture asserts that this is not the case. (In fact, he has promised a prize of $1000 for a solution) This webpage gives a compilation of what is known about this question; some of it can be found in Woodall's paper

- Examples of embeddings
- What would a counterexample look like?
- All cycles but the 4-cycle have embeddings.
- Known bounds on the number of edges vs. the number of vertices.
- On sequences of embeddings of the 4-path.
- Related output of a computerized search plus an
- Interpretation
- References.
- Additional Resources.

Here are perhaps the most simple thrackle embeddings of graphs with the same number of edges and vertices:

The graph embedded on the left is the 3-cycle. On the right
is shown an embedding of the graph with (n-2) edges meeting
at one vertex of a 3-cycle.
Note that only *straight* lines occur.
Below is an example which is necessarily drawn with
curved lines.

Back to top

- two cycles connected by a path (called
*Dumb-bell*) - three paths each connecting the same two points (called
*Theta*) - two cycles sharing a vertex (called
*Figure-8*)

Back to top

That the 4-cycle has no thrackle embedding is a straightforward application of Jordan's Theorem. The existence of thrackle embeddings of the cycles of order > 4 follows from the following statement and the existence of thrackle embeddings of the 3-cycle and the 6-cycle.

If a cycle of order N has a thrackle embedding, then so does the cycle of order N+2. We replace a 3-path by a 5-path and change the embedding in the following way:

The new lines are drawn sufficiently close to the original (dotted) line so that they intersect lines in the same order and orientation as the original line. Of course, the lines involved will be curved in general.

From the triangle we obtain embeddings of the odd cycles of order > 2. Here for example is the embedding of the 5-cycle:

Note that this embedding was obtained from a straight line embedding of the triangle and that it was possible to carry out the replacement procedure with straight lines. Applying it one more time will give a straight line embedding of the 7-cycle. There is no difficulty in seeing that just the odd cycles have straight-line embeddings.

Note also that, when one is just interested in the order and the direction in which
lines cross, there is essentially only one embedding of the
5-cycle. If the lines are numbered
in order of occurence along a traversal, then line **x**
meets lines **x+2, x-2 (mod 5)** in this order and
they hit line **x** in opposite directions. For cycles
of order > 5, there are many different kinds of embeddings.
(see further down)

To obtain embeddings of all even cycles of order > 4, we need to show an embedding of the 6-cycle. This can also be obtained from the triangle, but with a different method. Replace every line of an embedding by two lines in the following way:

When applied to an embedding of an odd cycle, this replacement yields an embedding of a cycle of doubled order. When applied to an embedding of an even cycle, this replacement yields an embedding of two copies of the cycle. For the triangle the result is an embedding of the 6-cycle:

Lovasz, Pach and Szegedy have shown that a bipartite graph can have a thrackle embedding only if it is planar. From Euler's polyhedral formula one readily obtains a bound on the number of edges with respect to the number of vertices for bipartite graphs with thrackle embeddings (roughly E < 3V). They sharpened this bound and proved that if a (possibly non-bipartite) graph with V vertices has a thrackle embedding then it has at most 2V - 3 edges.

Recently Cairns and Nikolayevsky have improved this bound: if a graph with V vertices has a thrackle embedding, then it has at most 1.5(V-1) edges.

In their paper, Lovasz, Pach and
Szegedy also show that
the theta **T(3,3,3)** formed by paths of length three has no thrackle embedding.
The proof relies on analyzing embeddings of the directed
4-path **1->2->3->4->5**. These are shown in the following diagram
(upto the operation of inverting of faces)

According to the order and the orientation with which the fourth line crosses the first and second line, the
embeddings are classified (by us) as zero, plus or minus. Note that
if the spots **1,2,3,4,5** are relabeled with **5,4,3,2,1**, respectively, the minus configurations become plus-configurations and vice versa; the zero configurations stay zero-configurations. In other words, a plus-configuration walked backwards is
a minus-configuration, and vice-versa, and a zero-configuration walked backwards is a zero-configuration.

The graph **T(3,3,3)** consists of
three 6-cycles each pair of which shares a 3-path. The directed 6-cycle (**1->2->3->4-5->6->1**) consists of six overlapping directed 4-paths: (**1->2->3->4->5, 2->3->4->5->6, ..., 6->1->2->3->4**).
In an embedding of a 6-cycle, which configurations
occur? Which sequences of configurations occur?

In proving that **T(3,3,3)** has no thrackle embedding Lovasz et.al. used the fact thata there is no zero-configuration in any embedding
of the 6-cycle, and
either there are only plus-configurations or only minus-configurations.

A C-program generated all thrackle embeddings of cycles of order 6 - 11 and analyzed which sequences of configurations occur. The results are shown below. Inspection of the embedding of the 5-cycle from above reveals that only zero-configurations occur. For the triangle the notion is not applicable and the 4-cycle has no embedding.

For the 6-cycle | Type 1 | + + + + + + |

For the 7-cycle | Type 1 | 0 0 0 0 0 0 0 |

Type 2 | 0 0 0 - 0 0 + | |

For the 8-cycle | Type 1 | 0 0 0 0 + + + + |

Type 2 | 0 0 + + + + + - | |

For the 9-cycle | Type 1 | 0 0 0 0 0 0 0 0 0 |

Type 2 | 0 0 0 0 0 0 0 + + | |

Type 3 | 0 0 0 0 0 0 - 0 + | |

Type 4 | 0 0 0 0 0 0 - 0 - | |

Type 5 | 0 0 0 0 0 - 0 0 + | |

Type 6 | 0 0 0 0 0 + 0 0 + | |

Type 7 | 0 0 0 0 0 + 0 0 - | |

Type 8 | 0 0 0 0 + 0 0 0 - | |

Type 9 | 0 0 0 + - 0 0 + + | |

Type 10 | 0 0 0 - - 0 0 + + | |

Type 11 | 0 0 + - 0 0 + 0 - |

The program found

Back to top

- It is not possible to connect the two open ends with two lines (obeying the constraints of thrackle embeddings).
- It is possible to connect them with three, or more lines (satisfying the constraints).

The thrackle conjecture is a similar problem. For example: draw an embedding of a 6-cycle and add two lines at an endpoint of a line so that they intersect all other lines exactly once. The conjecture asserts that it is not possible to connect the endpoints of these two lines obeying the rules of thrackle embeddings.

Back to top

- G.Cairns and Y.Nikolayevsky,
*Bounds for Generalized Thrackles*, Discrete and Computational Geometry, vol. 23 (2000), p. 191 - 206 - L.Lovasz, J.Pach, M.Szegedy,
*On Conway's Thrackle Conjecture*, in Proceedings of the 11th Annual Symposium on Computational Geometry, Vancouver, BC, Canada, June 1995. ACM Press 1995 Try www.math.nyu.edu/~pach/publications/thrackle.ps. - D.R. Woodall,
*Thrackles and Deadlock*, in Combinatorial Mathematics and its Applications (D.J.A. Welsh, ed.), Academic Press, London, p. 335 - 348

- Jon Perry's thrackle page.
- A section under Dan Archdeacon's Problems in Topological Graph Theory