Thrackles: An Improved Upper Bound
Radoslav Fulek JÃ¡nos Pach







IST Austria, Am Campus 1, Klosterneuburg 3400, Austria

radoslav.fulek@gmail.com
École Polytechnique Fédérale de Lausanne, Station 8, Lausanne 1015, Switzerland and Rényi Institute, Hungarian Academy of Sciences, 
P.O.Box 127 Budapest, 1364, Hungary 

 pach@cims.nyu.edu


Thrackles: An Improved Upper Bound
    Radoslav Fulek1The author greatfully acknowledges  support from Austrian Science Fund (FWF): M2281-N35. and János Pach2Supported by Swiss National Science Foundation Grants 200021-165977 and 200020-162884.
    December 30, 2023
=================================================================================================================================================================================================================




A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing.
We prove that any thrackle of n vertices has at most 1.3984n edges.
Quasi-thrackles are defined similarly, except that every pair of edges that do not share a vertex are allowed to cross an odd number of times. It is also shown that the maximum number of edges of a quasi-thrackle on n vertices is 3 2(n-1), and that this bound is best possible for infinitely many values of n.




§ INTRODUCTION


Conway's thrackle conjecture <cit.> is one of the oldest open problems in the theory of topological graphs. A topological graph is a graph drawn in the plane so that its vertices are represented by points and its edges by continuous arcs connecting the corresponding points so that (i) no arc passes through any point representing a vertex other than its endpoints, (ii) any two arcs meet in finitely many points, and (iii) no two arcs are tangent to each other. A thrackle is a topological graph in which any pair of edges (arcs) meet precisely once. According to Conway's conjecture, every thrackle of n vertices can have at most n edges. This is analogous to Fisher's inequality <cit.>: If every pair of edges of a hypergraph H have precisely one point in common, then the number of edges of H cannot exceed the number of vertices.

The first linear upper bound on the number of edges of a thrackle, in terms of the number of vertices n, was established in <cit.>. This bound was subsequently improved in <cit.> and <cit.>, with the present record, 1.4n, held by Goddyn and Xu <cit.>, which also appeared in the master thesis of the second author <cit.>. One of the aims of this note is to show that this latter bound is not best possible.



Any thrackle on n>3 vertices has at most 1.3984n edges.


Several variants of the thrackle conjecture have been considered. For example, Ruiz-Vargas, Suk, and Tóth <cit.> established a linear upper bound on the number of edges even if two edges are allowed to be tangent to each other. The notion of generalized thrackles was introduced in <cit.>: they are topological graphs in which any pair of edges intersect an odd number of times, where each point of intersection is either a common endpoint or a proper crossing. A generalized thrackle in which no two edges incident to the same vertex have any other point in common is called a quasi-thrackle. We prove the following.



Any quasi-thrackle on n vertices has at most
3/2(n-1) edges, and this bound is tight for infinitely many values of n.


The proof of Theorem <ref> is based on a refinement of parity arguments developed by Lovász et al. <cit.>, by Cairns–Nikolayevsky <cit.>, and by Goddyn–Xu  <cit.>, and it heavily uses the fact that two adjacent edges cannot have any other point in common. Therefore, one may suspect, as the authors of the present note did, that Theorem <ref> generalizes to quasi-thrackles. Theorem <ref> refutes this conjecture.




§ TERMINOLOGY



Given a topological graph G in the projective or Euclidean plane, if it leads to no confusion, we will make no distinction in notation or terminology between its vertices and edges and the points and arcs representing them.
A topological graph with no crossing is called an embedding. A connected component of the complement of the union of the vertices and edges of an embedding is called a face. A facial walk of a face is a closed walk in G obtained by traversing a component of the boundary of F. (The boundary of F may consist of several components.) The same edge can be traversed by a walk at most twice; the length of the walk is the number of edges counted with multiplicities. The edges of a walk form its support.

A pair of faces, F_1 and F_2, in an embedding are adjacent (or neighboring) if there exists at least one edge traversed by a facial walk of F_1 and a facial walk of F_2.
In a connected graph, the size of a face is the length of its (uniquely determined) facial walk.
A face of size k (resp., at least k or at most k) is called a k-face (resp., k^+-face and k^--face).

A cycle of a graph G is a closed walk along edges of G without vertex repetition. (To emphasize this property, sometimes we talk about “simple” cycles.)
A cycle of length k is called a k-cycle.

A simple closed curve on a surface is said to be one-sided if its removal does not disconnect the surface.
Otherwise, it is two-sided. An embedding of a graph G in the projective plane is called a parity embedding if every odd cycle of G is one-sided and every even cycle of G is two-sided.
In particular, in a parity embedding every face is of even size.





§ PROOF OF THEOREM <REF>







For convenience, we combine two theorems from <cit.> and <cit.>.



A graph G is a generalized thrackle if and only if  G admits a parity embedding in the projective plane.
In particular, any bipartite thrackle can be embedded in the (Euclidean) plane.



If G is a non-bipartite generalized thrackle, then, by a result of Cairns and Nikolayevsky <cit.>, it admits a  parity embedding in the projective plane.

On the other hand, Lovász, Pach, and Szegedy <cit.> showed that a bipartite graph is a generalized thrackle if and only if it is planar, in which case it
can be embedded in the projective plane so that every cycle is two-sided.


The proof of the next lemma is fairly simple and is omitted in this version.



A thrackle does not contain more than one triangle.


Refer to Fig. <ref>.
By Lemma <cit.>, every pair of triangles in a thrackle share a vertex.
A pair of triangles cannot share an edge, otherwise they would form a 4-cycle, and a thrackle cannot contain a 4-cycle, since 4-cycle is not a thrackle, which is easy to check.

Let T_1=vzy and T_2=vwu be two triangles that have a vertex v in common.
By Lemma <cit.>, the two closed curves representing T_1 and T_2 properly cross each other at v.
Hence, the closed Jordan curve C_1 corresponding to T_1 contains w in its exterior and u in its interior.
Thus, the drawing of T_1∪{uv,uw} in a thrackle is uniquely determined up to isotopy and the choice of the outer face.

If we traverse the edge wu from one endpoint to the other, we encounter its crossings  with the edges vy,yz, and zv in this or in the reversed order.
 Indeed, the crossings between wu and vz, and wu and vy must be in different
connected components of the complement of the union of zy,vw, and vu in the plane.
By symmetry, the crossing of zy and wu is on both zy and wu between the other two crossings.
Now, a simple case analysis reveals that this is impossible in a thrackle. We obtain a contradiction, which proves the lemma.


Next, we prove Theorem <ref> for triangle-free graphs. Our proof uses a refinement of the discharging method of Goddyn and Xu <cit.>.





Any triangle-free thrackle on n>3 vertices has at most 1.3984(n-1) edges.



Since no 4-cycle can be drawn as a thrackle, the lemma holds for graphs with fewer than 5 vertices.
We claim that a vertex-minimal counterexample to the lemma is (vertex) 2-connected.
Indeed, let G=G_1∪ G_2, where |V(G_1) ∩ V(G_2)|<2≤ |V(G_1)|,|V(G_2)|. Suppose that |V(G_1)|=n'.
By the choice of G, we have
|E(G)|=  |E(G_1)| + |E(G_2)| ≤  1.3984(n'-1)+1.3984(n-n') = 1.3984(n - 1).

Thus, we can assume that G is 2-connected.
Using Corollary <ref>, we can embed G as follows.
If G is not bipartite, we construct a  parity embedding of G
in the projective plane.
If G is bipartite, we construct an embedding of G in the Euclidean plane.
Note that in both cases, the size of each face of the embedding is even.

The following statement can be verified by a simple case analysis. It was removed from the short version of this note.






In the parity embedding of a 2-connected thrackle in the projective plane, the facial walk of every 8^--face is a cycle, that is, it has no repeated vertex.


If G is bipartite, the claim follows by the 2-connectivity of G and by the fact that the 4-cycle is not a thrackle.

Suppose G is not bipartite. Then G cannot contain 4^--face,
since we excluded triangles (by the hypothesis of the lemma) and 4-cycles (which are not thrackles).
We can also exclude any 5-face F, because either the facial walk of F is a 5-cycle, which is impossible in a parity embedding, or the facial walk contains a triangle.

Analogously, if F is a 7-face, its facial walk cannot be a  cycle (with no repeated vertex).
Hence, the support of F must contain a 5-cycle. Using the fact that G has no
triangle and 4-cycle, we conclude that F must be incident to a cut-vertex, a contradiction.

It remains to deal with 6-faces and 8-faces.
If the facial walk of a 6-face F is not a 6-cycle, then its support is a path of length three or a 3-star. In this case, G is a tree on three vertices, contradicting our assumption that G is 2-connected. Thus, the facial walk of every 6-face must be a 6-cycle.

The support of the facial walk of an 8-face F cannot contain a 5-cycle, because in this case it would also contain a triangle. Therefore, the support of F must contain a 6-cycle. The remaining (2-sided) edge of F cannot be a diagonal of this cycle (as then it would create a triangle or a 4-cycle), and it cannot be a “hanging” edge (because this would contradict the 2-connectivity of G). This completes the proof of the proposition.



To complete the proof of Lemma <ref>, we use a discharging argument.
Since G is embedded in the projective plane, by Euler's formula
we have

    e+1≤ n+f

where f is the number of faces and e is the number of edges of the embedding.

We put a charge d(F) on each face F of G, where d(F) denotes the size of F, that is, the length of its facial walk.
An edge is called bad if it is incident to a 6-face.
Let F be an 8^+-face.
Through every bad edge uv of F, we discharge from its charge a  charge of 1/6 to the neighboring 6-face on the other side of uv.

We claim that every face ends up with a charge  at least 7.
Indeed, we proved in <cit.> that in a thrackle no pair of 6-cycles can share a vertex.
By Proposition <ref>, G has no 8-face with 7 bad edges. Furthermore, every 8^--face is a 6-face or an 8-face, since in a parity embedding there is no odd face, and 4-cycles are not thrackleable.




Unless G has 12 vertices and 14 edges, no two 8^+-faces that share an edge can end up with charge precisely 7.



An 8-face F with charge 7 must be adjacent to a pair of 6-faces, F_1 and F_2.
By Proposition <ref>, the facial walks of F,F_1, and F_2 are cycles. Since G does not contain a cycle of length 4, both F_1 and F_2 share three edges with F, or one of them shares two edges with F and the other one four edges. Hence, any 8-face F' adjacent to F shares an edge uv with
F, whose both endpoints are incident to a 6-face.
If F' has charge 7, both edges adjacent to uv along the facial walk F' must be incident to a 6-face. By the aforementioned result from <cit.>,
these 6-faces must be F_1 and F_2. By Proposition <ref>, the facial walk of F' is an 8-cycle.
Since F' shares 6 edges with F_1 and F_2, we obtain that G
has only 4 faces F,F',F_1, and F_2.


In the case where G has 12 vertices and 14 edges, the lemma is true.
By Proposition <ref>, if a pair of 8^+-faces share an edge, at least one of them ends up with a charge at least 43/6. Let F be such a face. We can further discharge 1/24 from the charge of F to each neighboring 8^+-face. After this step, the remaining charge of F is at least 43 6-31 24=7+1 24, which is possibly attained only by an 8-face that shares 5 edges with 6-faces. Every 9^+-face F' has charge at least d(F')-d(F') 6≥ 7+1 2.












In the last discharging step, we discharge through each bad edge of an 8^+-face an additional charge of 1/288 to the neighboring 6-face. At the end, the charge of every face is at least 7+1 24-61 288=7+1 48. Since the total charge ∑_F d(F)=2e has not changed during the procedure, we obtain
2e≥ (7+1 48)f. Combining this with (<ref>), we conclude that 
    e≤7+1 48/5+1 48n-7+1 48/5+1 48≤ 1.3984(n-1),

which completes the proof of Lemma <ref>.

Now we are in a position to prove Theorem <ref>.




Proof of Theorem <ref>. 

 If G does not contain a triangle, we are done by Lemma <ref>.
Otherwise, G contains a triangle T. We remove an edge of T from G
and denote the resulting graph by G'.
According to Lemma <ref>, G' is triangle-free.
Hence, by Lemma <ref>, G' has at most 1.3984(n-1) edges, and
it follows that G has at most 1.3984(n-1)+1<1.3984n edges.








Without introducing any additional forbidden configuration, our methods cannot lead to an upper bound in  Theorem <ref>, better than 22 16n=1.375n.


This is a simple consequence of the next lemma.
Let H(k) be a graph obtained by taking the union of a pair of vertex-disjoint paths P=p_1… p_6k and Q=q_1… q_6k
 of length 6k; edges p_iq_i for all i 3= 0; edges p_iq_6k-i for all i 3 = 2; and paths p_ip_i'p_i”q_i, for all i 3=1, which are internally
 vertex-disjoint from P, Q, and from one another.



 

For every k∈ℕ, the graph H(k) has 16k vertices and 22k-2 edges, it contains no two 6-cycles that share a vertex or are joined by an edge, and  it
admits a parity embedding in the projective plane.


For every k, H(k) has 12k-4 vertices of degree three and 4k+4 vertices of degree two.
Thus, H(k) has 3(6k-2)+4k+4=22k-2 edges.
A projective embedding of G(k) with the required property is depicted in Figure <ref>.
Using the fact that all 6-cycles are facial, the lemma follows.



It was stated without proof in  <cit.> that the thrackle conjecture has been verified by computer up to n=11. Provided that this is true, the upper bound in Theorem <ref> can be improved to
e≤7+1 5/5+1 5(n-1)≤ 1.3847(n-1). This follows from the fact that in this case an 8-face and a 6-face can share at most
one edge and therefore we can maintain a charge of at least 7+1/5 on every face.
Indeed, we change our discharging procedure so that we just send to every 6-face  a charge of 1/5 from every neighboring face. Since an 8-face has at most four 6-faces as its neighbors, also every 8^+-face ends up with a charge of at least 7+1/5  as required. 




§ PROOF OF THEOREM <REF>



It is known <cit.> that C_4, a cycle of length 4, can be drawn as a generalized thrackle.
Hence, our next result whose simple proof is left to the reader implies that the class of quasi-thrackles forms a proper subclass of
the class of generalized thrackles.






C_4 cannot be drawn as a quasi-thrackle.


Suppose for contradiction that C_4=uvwz can be drawn as a quasi-thrackle; see Fig. <ref>.
Assume without loss of generality that in the corresponding drawing, the path uvw a path uvw does not intersect itself.
Let c_1 denote the first crossing along uz (with vw) on the way from u.
Let c_2 denote the first crossing along wz (with uv) on the way from w.
Let C_u denote the closed Jordan curve consisting of uv; the portion of
uz between u and c_1; and the portion of vw between v and c_1.
Let C_w denote the closed Jordan curve consisting of vw; the portion of
wz between w and c_2; and the portion of uv between v and c_2.

Observe that z and w are not contained in the same connected component of the complement
of C_u in the plane. Indeed, wz crosses C_u an odd number of times, since it can cross
it only in uv. Let 𝒟_u denote the connected component of the complement
of C_u containing z. By a similar argument,
z and u are not contained in the same connected component
of the complement of C_w in the plane. Let 𝒟_w denote the connected component of the complement
of C_w  containing z.

Since z∈𝒟_u ∩𝒟_w, we have that 𝒟_u ∩𝒟_w ≠∅.
On the other hand, C_u and C_w do not cross each other, but they share a Jordan arc containing neither u nor w.
If  𝒟_u ⊂𝒟_w (or 𝒟_w ⊂𝒟_u),
then u and z are both in 𝒟_w (or w and z are both in 𝒟_u), which is impossible.
Otherwise, u and z are both in 𝒟_w, and at the same time w and z are both in 𝒟_u, which is again a contradiction.



Let G(k) denote a graph consisting of k pairwise edge-disjoint triangles that intersect in a single vertex.
The drawing of G(3) as a quasi-thrackle, depicted in Figure <ref>, can be easily generalized to any k. Therefore, we obtain the following


For every k, the graph G(k) can be drawn as a quasi-thrackle.


In view of Lemma <ref>, G_k cannot be drawn as a thrackle for any k>1.
Thus, the class of thrackles is
a proper sub-class of the class of quasi-thrackles.







Cairns and Nikolayevsky <cit.> proved that every generalized thrackle of n vertices has at most 2n-2 edges, and that this bound cannot be improved.
The graphs G(k) show that for n=2k+1, there exists a quasi-thrackle with n vertices and with 3/2(n-1) edges. According to Theorem <ref>, no quasi-thrackle with n vertices can have more edges.






Proof of Theorem <ref>. 
 Suppose that the theorem is false, and let G be a counterexample with the minimum number n of vertices.


We can assume that G is 2-vertex-connected.
Indeed, otherwise G=G_1∪ G_2, where |V(G_1) ∩ V(G_2)|≥ 1
and E(G_1) ∩ E(G_2)=∅. Suppose that |V(G_1)|=n'.
By the choice of G, we have
|E(G)|=  |E(G_1)| + |E(G_2)| ≤3/2(n'-1)+3/2(n-n') = 3/2(n - 1), so G is not a counterexample.

Suppose first that G is bipartite. By Corollary <ref>, G (as an abstract graph) can be embedded in the Euclidean plane.
By Lemma <ref>, all faces in this embedding are of size at least 6. Using a standard double-counting argument, we obtain that 2e≥ 6f, where e and f are the number of edges and faces of G, respectively. By Euler's formula, we have e+2=n+f. Hence, 6e+12≤ 6n+2e, and rearranging the terms we obtain e≤3 2(n-6), contradicting our assumption that G was not a counterexample.

If G is not bipartite, then, according to Corollary <ref>, it has a parity embedding in the
projective plane. By Lemma <ref>, G contains no 4-cycle. It does not have loops and multiple edges, therefore, the embedding has no 4-face. G cannot have a 5-face, because the facial walk of a 5-face would be either a one-sided 5-cycle (which is impossible), or it would contain a triangle and a cut-vertex (contradicting the 2-connectivity of G). The embedding of G also does not have a 3-face, since G is bipartite. By Euler's formula, e+1=n+f and, as in the previous paragraph, we conclude that 6e+6≤ 6n+2e, the desired contradiction.








plain





§ OMITTED PROOFS






Lemma<ref>
A thrackle does not contain more than one triangle.


Refer to Fig. <ref>.
By Lemma <cit.>, every pair of triangles in a thrackle share a vertex.
A pair of triangles cannot share an edge, otherwise they would form a 4-cycle, and a thrackle cannot contain a 4-cycle, since 4-cycle is not a thrackle, which is easy to check.

Let T_1=vzy and T_2=vwu be two triangles that have a vertex v in common.
By Lemma <cit.>, the two closed curves representing T_1 and T_2 properly cross each other at v.
Hence, the closed Jordan curve C_1 corresponding to T_1 contains w in its interior and u in its exterior.
Thus, the drawing of T_1∪{uv,uw} in a thrackle is uniquely determined up to isotopy and the choice of the outer face.

If we traverse the edge wu from one endpoint to the other, we encounter its crossings  with the edges vy,yz, and zv in this or in the reversed order.
 Indeed, the crossings between wu and vz, and wu and vy must be in different
connected components of the complement of the union of zy,vw, and vu in the plane, see Fig. <ref> right.
By symmetry, the crossing of zy and wu is on both zy and wu between the other two crossings.
However, this is impossible in a thrackle. We obtain a contradiction, which proves the lemma.


Proposition<ref>
In the parity embedding of a 2-connected thrackle in the projective plane, the facial walk of every 8^--face is a cycle, that is, it has no repeated vertex.


If G is bipartite, the claim follows by the 2-connectivity of G and by the fact that the 4-cycle is not a thrackle.

Suppose G is not bipartite. Then G cannot contain 4^--face,
since we excluded triangles (by the hypothesis of the lemma) and 4-cycles (which are not thrackles).
We can also exclude any 5-face F, because either the facial walk of F is a 5-cycle, which is impossible in a parity embedding, or the facial walk contains a triangle.

Analogously, if F is a 7-face, its facial walk cannot be a  cycle (with no repeated vertex).
Hence, the support of F must contain a 5-cycle. Using the fact that G has no
triangle and 4-cycle, we conclude that F must be incident to a cut-vertex, a contradiction.

It remains to deal with 6-faces and 8-faces.
If the facial walk of a 6-face F is not a 6-cycle, then its support is a path of length three or a 3-star. In this case, G is a tree on three vertices, contradicting our assumption that G is 2-connected. Thus, the facial walk of every 6-face must be a 6-cycle.

The support of the facial walk of an 8-face F cannot contain a 5-cycle, because in this case it would also contain a triangle. Therefore, the support of F must contain a 6-cycle. The remaining (2-sided) edge of F cannot be a diagonal of this cycle (as then it would create a triangle or a 4-cycle), and it cannot be a “hanging” edge (because this would contradict the 2-connectivity of G). This completes the proof of the proposition.


















Lemma<ref>
C_4 cannot be drawn as a quasi-thrackle.



Suppose for contradiction that C_4=uvwz can be drawn as a quasi-thrackle; see Fig.3.
Assume without loss of generality that in the corresponding drawing, the path uvw a path uvw does not intersect itself.
Let c_1 denote the first crossing along uz (with vw) on the way from u.
Let c_2 denote the first crossing along wz (with uv) on the way from w.
Let C_u denote the closed Jordan curve consisting of uv; the portion of
uz between u and c_1; and the portion of vw between v and c_1.
Let C_w denote the closed Jordan curve consisting of vw; the portion of
wz between w and c_2; and the portion of uv between v and c_2.



Observe that z and w are not contained in the same connected component of the complement
of C_u in the plane. Indeed, wz crosses C_u an odd number of times, since it can cross
it only in uv. Let 𝒟_u denote the connected component of the complement
of C_u containing z. By a similar argument,
z and u are not contained in the same connected component
of the complement of C_w in the plane. Let 𝒟_w denote the connected component of the complement
of C_w  containing z.

Since z∈𝒟_u ∩𝒟_w, we have that 𝒟_u ∩𝒟_w ≠∅.
On the other hand, C_u and C_w do not cross each other, but they share a Jordan arc containing neither u nor w.
If  𝒟_u ⊂𝒟_w (or 𝒟_w ⊂𝒟_u),
then u and z are both in 𝒟_w (or w and z are both in 𝒟_u), which is impossible.
Otherwise, u and z are both in 𝒟_w, and at the same time w and z are both in 𝒟_u, which is again a contradiction.




