Fleischner's theorem
In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle.
It is named after Herbert Fleischner, who published its proof in 1974.
is Hamiltonian if it contains a cycle that touches each of its vertices exactly once.
It is 2-vertex-connected if it does not have an articulation vertex, a vertex whose deletion would leave the remaining graph disconnected.
Fleischner's theorem states that the square of a finite 2-vertex-connected graph with at least three vertices must always be Hamiltonian.
Equivalently, the vertices of every 2-vertex-connected graph
In Fleischner's theorem, it is possible to constrain the Hamiltonian cycle in
[1] In addition to having a Hamiltonian cycle, the square of a 2-vertex-connected graph
must also be Hamiltonian connected (meaning that it has a Hamiltonian path starting and ending at any two designated vertices) and 1-Hamiltonian (meaning that if any vertex is deleted, the remaining graph still has a Hamiltonian cycle).
is not 2-vertex-connected, then its square may or may not have a Hamiltonian cycle, and determining whether it does have one is NP-complete.
[4] An infinite graph cannot have a Hamiltonian cycle, because every cycle is finite, but Carsten Thomassen proved that if
is an infinite locally finite 2-vertex-connected graph with a single end then
necessarily has a doubly infinite Hamiltonian path.
is locally finite, 2-vertex-connected, and has any number of ends, then
In a compact topological space formed by viewing the graph as a simplicial complex and adding an extra point at infinity to each of its ends, a Hamiltonian circle is defined to be a subspace that is homeomorphic to a Euclidean circle and covers every vertex.
[6] The Hamiltonian cycle in the square of an
-vertex 2-connected graph can be found in linear time,[7] improving over the first algorithmic solution by Lau[8] of running time
Fleischner's theorem can be used to provide a 2-approximation to the bottleneck traveling salesman problem in metric spaces.
[9] A proof of Fleischner's theorem was announced by Herbert Fleischner in 1971 and published by him in 1974, solving a 1966 conjecture of Crispin Nash-Williams also made independently by L. W. Beineke and Michael D.
[10] In his review of Fleischner's paper, Nash-Williams wrote that it had solved "a well known problem which has for several years defeated the ingenuity of other graph-theorists".
[11] Fleischner's original proof was complicated.
Václav Chvátal, in the work in which he invented graph toughness, observed that the square of a
-tough; he conjectured that 2-tough graphs are Hamiltonian, from which another proof of Fleischner's theorem would have followed.
[12] Counterexamples to this conjecture were later discovered,[13] but the possibility that a finite bound on toughness might imply Hamiltonicity remains an important open problem in graph theory.
A simpler proof both of Fleischner's theorem, and of its extensions by Chartrand et al. (1974), was given by Říha (1991),[14] and another simplified proof of the theorem was given by Georgakopoulos (2009a).
