# What is known about the Thrackle Problem

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

### Contents

(Collaboration with Luis Goddyn)

### 1. Two examples

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.

### 2. What would a counterexample look like?

It is rather easy to see that a counterexample (if it exists) to the conjecture has to contain two cycles, and that a counterexample with the minimal number of vertices would either be
• 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)
Mike Rubinstein (unpublished) showed that if there is a counterexample of any one of these three kinds, then there are counterexamples of all three kinds.

### 3. All cycles but the 4-cycle have embeddings

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. 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.

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: ### 4. Known bounds on the number of edges vs. number of vertices

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.

### 5. Sequences of embeddings of the 4-path

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.

### 6. Output of a computerized search

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.

#### Realised sequences

 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

### 7. Interpretation

The table above tells us that the zero configuration cannot be found in an embedding of the 6-cycle, but it can be found for example in an embedding of the 8-cycle. Look at one of the zero configurations. From the table we read of the following two facts:
• 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).
In this manner, the table provides us with many more examples of embeddings of paths which can only be completed to an embedding of a cycle with a certain minimal number of lines.

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.