Conway's thrackle conjecture
Encyclopedia
A thrackle is an embedding
(in the plane) of a graph
, such that each edge is a Jordan arc
and every pair of edges meet once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be transverse.
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 C4 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.
Lovász et al. proved that every bipartite
thrackle is a planar graph
, although not drawn in a planar way. As a consequence, they show that every thrackleable graph with n vertices has at most 2n − 3 edges. Since then, this bound has been improved two times. First, it was improved to 3(n − 1)/2, and the current best bound is roughly 1.428n. Moreover, the method used to prove this result yields for any ε>0 a finite algorithm that either
improves the bound to (1 + ε)n or disproves the conjecture.
If the conjecture is false, a minimal counterexample would have the form of two even cycles sharing a vertex. Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.
Embedding
In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
(in the plane) of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
, such that each edge is a Jordan arc
Curve
In mathematics, a curve is, generally speaking, an object similar to a line but which is not required to be straight...
and every pair of edges meet once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be transverse.
John H. Conway
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
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
Pseudoforest
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...
. 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 C4 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.
Lovász et al. proved that every bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
thrackle is a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
, although not drawn in a planar way. As a consequence, they show that every thrackleable graph with n vertices has at most 2n − 3 edges. Since then, this bound has been improved two times. First, it was improved to 3(n − 1)/2, and the current best bound is roughly 1.428n. Moreover, the method used to prove this result yields for any ε>0 a finite algorithm that either
improves the bound to (1 + ε)n or disproves the conjecture.
If the conjecture is false, a minimal counterexample would have the form of two even cycles sharing a vertex. Therefore, to prove the conjecture, it would suffice to prove that graphs of this type cannot be drawn as thrackles.