Known Bounds
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.
Read more about this topic: Conway's Thrackle Conjecture
Famous quotes containing the word bounds:
“Nature seems at each man’s birth to have marked out the bounds of his virtues and vices, and to have determined how good or how wicked that man shall be capable of being.”
—François, Duc De La Rochefoucauld (1613–1680)
“Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man’s appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded.”
—Abraham Lincoln (1809–1865)