Every two edges must meet

All the drawings of a graph discussed so far have tried to keep edges apart. Two graphs that will not lie flat asks when crossings can be avoided altogether, and the crossings a graph cannot avoid counts how few are forced when they cannot. In the 1960s John Conway turned the question over and asked for the opposite extreme. Draw a graph on the plane so that every two edges meet exactly once. They may share an endpoint, or they may cross at one point, and those are the only two options. Two edges may not miss each other, and they may not meet twice.

He called such a drawing a thrackle, an old northern word for a tangle in a fishing line. The question is what such a drawing permits. The stars in the figure below are thrackles: all the edges in the 5-pointed star cross or share an end with every other. Conway’s conjecture is that in a thrackle, the number of edges never exceeds the number of points. Planar graphs have at most about three edges per point. This looks as if it ought to be a much easier question, with a smaller count. Conway offered a prize for a proof and the problem has been open for more than sixty years.

Odd and even #

The figure’s stars reach the conjectured bound with equality. Each is a regular polygon with an odd number $n$ of corners, joining each corner to the two nearly opposite ones. With $n$ corners that makes a single closed star of $n$ edges and the $\binom{n}{2}$ pairs of edges, which is 36 at $n = 9$, all meet. All were checked exactly. The reason they work is that in an odd polygon the nearly-opposite chords through any two corners must interleave around the circle or share a corner, so no two can miss.

Even cycles are different. A cycle of four edges cannot be a thrackle, even with curved edges. In a 4-cycle $a, b, c, d$, each edge shares a corner with two others and has to cross the third, and the argument that this is impossible is a short exercise in which side of a closed curve a point lies on, since two closed curves in a plane cross an even number of times. So a thrackle cannot contain a 4-cycle.

The straight-line version is easy to test, and it fails on all 20,000 random quadrilaterals tried. Even stars of 6 and 8 points cannot close the same way: in the figure, the marked edges are pairs that never meet. But here the curved world starts to differ. A 6-cycle cannot be drawn as a straight thrackle, and it can be drawn as a curved one. Douglas Woodall showed in 1969 that the 4-cycle is the only cycle that is not thrackleable in the curved sense: every other cycle, odd or even, can be drawn with every two edges meeting exactly once. Curved edges have much more freedom, and the conjecture has to hold against all of that freedom.

What straight edges cannot do #

For straight edges there is a clean proof that the bound holds. It starts with one observation about a fan. Suppose a point $v$ has at least three edges in the thrackle, $va$, $vb$ and $vc$. Since all three meet at $v$, they cannot meet anywhere else, as straight segments. Among any three rays from a point, there is always one whose line has the other two on opposite sides; call that one the middle edge, $vb$.

Now look at the far end $b$. Any other edge leaving $b$ would have to meet both $va$ and $vc$. A straight segment starting at $b$, and not running back along the line through $v$, stays on one side of that line, and $va$ and $vc$ lie on opposite sides of it. So it cannot meet both. So $b$ has no other edge. The far end of a middle edge has degree one.

So whenever some point has three edges, a point of degree one exists, and removing it takes away one edge and one point together. That preserves the excess of edges over points. Repeat until no point has three edges. Every point then has at most two, so what is left is a collection of cycles and paths, whose number of edges is at most the number of points. That gives $|E| \le n$. In the figure, nine random points have nine edges, of which six edges with their six end points are peeled off, and what is left is a triangle.

The result goes back to a different question. Heinz Hopf and Erika Pannwitz posed a problem about the set of distances in a plane in 1934, to which this is the solution. It is a beautiful side-effect that a theorem stated for tangles was first proved for a question about longest distances, thirty years before the word thrackle.

Longest distances form a thrackle #

Take any finite set of points in the plane, and join each pair at the greatest distance that occurs. How many such pairs can there be? For a circle of $n$ evenly spaced points with $n$ even, there are $n/2$ diameters. With $n$ odd, the odd star gives $n$. Hopf and Pannwitz showed that $n$ is the maximum.

The reason is that two longest segments must meet. Suppose $ab$ and $cd$ are both of the greatest length and share no point. They then cannot cross, and it can be shown that among the four endpoints some pair is further apart than the greatest length, by looking at the convex hull of the four points. Hence the graph of longest distances is a straight thrackle, and so has at most $n$ edges.

The tests in the figure confirm this on the odd regular polygons and on four hundred sets of twelve random points with coordinates on a grid, chosen so that several pairs would tie at the longest distance, and in every case each two longest segments meet. This fact has a strong consequence for one of the best-known problems in geometry. Borsuk’s question asks how many pieces of smaller diameter a set must be cut into. In the plane, the answer of three is equivalent to saying that the graph of diameters can be coloured with three colours, so that the pieces do not contain a longest pair. A thrackle with at most as many edges as points has at most one odd cycle in each component, so three colours suffice for it. It is the same object seen from another angle: Borsuk’s problem in the plane is a statement about thrackles.

The same observation also fails in the expected way one dimension up. In three-space, Andrew Vázsonyi conjectured that there are at most $2n - 2$ longest distances, and this was proved around 1957 by Branko Grünbaum, Aladár Heppes and Stefan Straszewicz. In four dimensions and above, the count becomes quadratic, like the number of unit distances in some configurations. Then longest segments no longer need to cross at all, since points can be placed on two orthogonal circles, with all the distances between the circles equal.

A search over sets of edges #

It is possible to compute the largest straight thrackle exactly for small random sets of points. Form a new graph in which each node is an edge of the complete graph on the points, and join two nodes if the edges meet. A thrackle is a set of mutually joined nodes, a clique. Finding a maximum clique is hard in general, but for ten points there are only 45 nodes, and a simple branch and bound handles it at once.

This example reaches exactly nine edges, and most of them fan out from a single point. It is typical of what the search returns: the fan gives $n - 1$ edges at once, since edges sharing a point always meet, and all that is needed for one more edge is a crossing edge that meets every edge of the fan. That is why the bound is so often reached, and why the extremal examples are not interesting in themselves. Thrackles are characterised by what cannot be added.

The table shows the results for several thousand random point sets. In none does the maximum exceed the number of points. At four points, 433 of 600 sets reach four edges, and the rest have three. Those are the sets with one point inside the triangle of the others: a convex quadrilateral has a triangle and a crossing edge that makes four, and a point inside a triangle has neither. By ten points, all 200 sets reach ten. The result confirms the theorem and it makes the point that the difficulty lies in curved edges and not here. If the straight conjecture were the whole story, this would be a footnote. The curved version is what has held out.

Curved edges and how far the bound has come #

For curves the argument above collapses at its first step. Two curved edges from a point $v$ do not define a wedge that a third curve must respect; a curve from the far end $b$ can wind around and cross both $va$ and $vc$. Nothing forces $b$ to have degree one. So the bound has to be attacked by other means, and progress has been slow.

László Lovász, János Pach and Mario Szegedy gave the first linear bound in 1997: at most $2n - 3$ edges. Their method used a parity argument, and it depended on two facts: thrackles have no 4-cycle, and a thrackle that is bipartite can be transformed into a planar graph by repeatedly reflecting parts of it. That is a remarkable connection, since planar graphs and thrackles are at opposite ends of the crossing spectrum. Grant Cairns and Yury Nikolayevsky improved the bound to $\tfrac32(n - 1)$ in 2000, by extending the method. Radoslav Fulek and János Pach lowered it to about $1.43n$ in 2011 with a careful analysis, and more recent work has shaved further. Each step has been in the leading constant. None has reached 1.

The conjecture is also known for several restricted classes of drawing. It is true for $x$-monotone thrackles, in which each edge is drawn as a function graph, proved by Pach and Ethan Sterling in 2011, and for outerplanar thrackles, whose points lie on a circle with all edges inside. It is true for drawings in which edges are spirals of a suitable kind, as studied by Cairns and Nikolayevsky. Each of these special cases has a separate proof, each exploiting some special structure, and none of those proofs extends to the general situation. And there is an equivalent statement due to Woodall: if the conjecture holds, a finite graph can be thrackled exactly when it has at most one odd cycle in each connected part and contains no 4-cycle, apart from a few small exceptions, and the theorem would then be a full description rather than a bound.

An opposite of planarity #

Planarity is an unusual property in that a graph’s own combinatorial structure decides it, through Kuratowski’s two forbidden graphs and the minors that contain them. The thrackle property looks like a mirror image. And there is a sense in which that is correct: the reflection trick used by Lovász, Pach and Szegedy literally turns a bipartite thrackle into a planar drawing by repeatedly flipping edges. A bipartite graph is therefore thrackleable only if it is planar, and the same condition with restrictions works the other way.

Then the 4-cycle is the case that says the mirror is not perfect. It is planar and is not thrackleable, because the two pairs of opposite edges would each have to cross and the parity of crossings between two closed curves forbids it. Thrackles impose a global parity condition that planarity does not see, and that is where the difficulty in proofs comes from. Euler’s formula gives planarity a sharp bound of $3n - 6$ edges, using faces and counting, and the same formula supplies the bounds of the crossing lemma. A thrackle has no faces of the helpful kind. Its regions are small and numerous, with most of the information about them locked in crossings. So there is no analogue of Euler’s count to hand, and the proofs that exist go via parity and transformation.

The most crossings a graph can have #

The word extremal applies in a precise way here, and it comes from the other direction. The crossing number of a graph is the least number of crossings over all its drawings. There is an obvious companion, the maximum crossing number, with some restriction to keep it finite: edges may not cross twice, and edges sharing an end may not cross at all, which are exactly the rules of a good drawing. Under those rules each pair of edges with no shared end contributes at most one crossing, so a graph with $m$ edges and degrees $d_1, \dots, d_n$ has at most

$$\binom{m}{2} - \sum_i \binom{d_i}{2}$$

crossings. This is called the thrackle bound, and a graph attains it exactly when it has a thrackle drawing, since a thrackle is precisely a drawing where every allowed crossing happens. The nine-pointed star has 36 pairs of edges, of which 9 share a corner, and so it has 27 crossings, all of them forced: there is no drawing of a 9-cycle with more.

So the conjecture has a second reading, that the graphs attaining this upper bound on crossings must be sparse. The crossing lemma says that graphs with many edges must have many crossings, and its opposite number here says that a graph cannot have every crossing it is entitled to unless it has few edges. The first is a theorem whose proof takes half a page and uses a random sample of the points. The second has resisted everything for sixty years. A good drawing of a graph with more edges than points must leave some pair of edges uncrossed, and no known argument says which pair.

What the search covers #

The exact searches are complete on each point set but they sample only random point sets, so they say nothing about specially constructed sets beyond the theorem, and random sets almost never have the delicate alignments that might matter. Sets on a circle and on a grid were tested too, in the figure on longest distances. The search treats a shared endpoint and a crossing as the only two ways to meet, and considers points in general position; three collinear points would need extra care, and the random sets avoid them with probability one.

Nothing computed here touches curved thrackles. All statements about curved edges, the $2n - 3$ bound and the improvements on it, and Woodall’s characterisation are cited from the literature. The peeling proof for straight edges is given in outline and is correct as stated for segments, and the figure shows one run of it, not a proof. The longest-distance statement was tested only in the plane, and the three-dimensional results are quoted.

Still open: the conjecture itself #

Does every thrackle have at most as many edges as points? No counterexample is known, and computer searches have confirmed it for small numbers of points, through a difficult enumeration of topological drawings. A proof that the constant 1.43 can be reduced to 1 is not in sight. The improvements to date have been of the type that pushes a linear programme’s optimum down by finding one more local configuration to exclude, and each has been more labour for a smaller gain.

A more accessible question is about the structure of a counterexample, if one exists. Any such graph would need to contain two cycles of even length that are disjoint or share only a vertex. It has been shown that a minimal counterexample would have to have certain rare properties, so it would be highly constrained. Nobody knows if those constraints are mutually contradictory.

A fan, a middle edge and a parity #

In a straight thrackle, the far end of a middle edge at any point of degree three has no other edge, so peeling it reduces edges and points together, and that alone proves $|E| \le n$. The set of longest distances in the plane is a thrackle, which also gives a three-colouring and settles Borsuk’s question in two dimensions. Random sets of points reach the bound routinely, because a fan gets most of the way there without trying. The computation confirms all of this up to ten points.

The whole of the difficulty is in a curve’s freedom to wind. A curved edge has no fan to fall inside, and so the local reason disappears and only parity survives, and Conway’s sentence-long conjecture has been waiting since the 1960s for a replacement.