
In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
to contain a
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
. It states that, if is a
2-vertex-connected graph, then the
square of is Hamiltonian. it is named after
Herbert Fleischner
Herbert Fleischner (* January 29, 1944 in London) is an Austrian mathematician. Education and career
Fleischner moved to Vienna with his parents in 1946. He attended primary and secondary school in Vienna, graduating in 1962. After that he studied ...
, who published its proof in 1974.
Definitions and statement
An
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
''G'' is Hamiltonian if it contains a
cycle
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in soc ...
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. Not every 2-vertex-connected graph is Hamiltonian; counterexamples include the
Petersen graph
In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
and the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
''K''
2,3.
The square of ''G'' is a graph ''G''
2 that has the same vertex set as ''G'', and in which two vertices are adjacent if and only if they have distance at most two in ''G''. 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 ''G'' may be arranged into a
cyclic order such that adjacent vertices in this order are at distance at most two from each other in ''G''.
Extensions
In Fleischner's theorem, it is possible to constrain the Hamiltonian cycle in ''G''
2 so that for given vertices ''v'' and ''w'' of ''G'' it includes two edges of ''G'' incident with ''v'' and one edge of ''G'' incident with ''w''. Moreover, if ''v'' and ''w'' are adjacent in ''G'', then these are three different edges of ''G''.
In addition to having a Hamiltonian cycle, the square of a 2-vertex-connected graph ''G'' must also be Hamiltonian connected (meaning that it has a
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
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). It must also be vertex
pancyclic, meaning that for every vertex ''v'' and every integer ''k'' with 3 ≤ ''k'' ≤ , ''V''(''G''), , there exists a cycle of length ''k'' containing ''v''.
If a graph ''G'' 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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
.
An infinite graph cannot have a Hamiltonian cycle, because every cycle is finite, but
Carsten Thomassen proved that if ''G'' is an infinite locally finite 2-vertex-connected graph with a single
end then ''G''
2 necessarily has a doubly infinite Hamiltonian path. More generally, if ''G'' is locally finite, 2-vertex-connected, and has any number of ends, then ''G''
2 has a Hamiltonian circle. In a
compact topological space
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i.e ...
formed by viewing the graph as a
simplicial complex
In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their ''n''-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial ...
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.
Algorithms
The Hamiltonian cycle in the square of an ''n''-vertex 2-connected graph can be found in linear time, improving over the first algorithmic solution by Lau of running time ''O(n
2)''.
Fleischner's theorem can be used to provide a
2-approximation to the
bottleneck traveling salesman problem in
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general sett ...
s.
History
A proof of Fleischner's theorem was announced by
Herbert Fleischner
Herbert Fleischner (* January 29, 1944 in London) is an Austrian mathematician. Education and career
Fleischner moved to Vienna with his parents in 1946. He attended primary and secondary school in Vienna, graduating in 1962. After that he studied ...
in 1971 and published by him in 1974, solving a 1966 conjecture of
Crispin Nash-Williams also made independently by
L. W. Beineke
Lowell Wayne Beineke (born 1939) is a professor of graph theory at Purdue University Fort Wayne. Beineke is known for his elegant characterization of line graphs (derived graph) in terms of the nine Forbidden graph characterization.
Beineke has t ...
and
Michael D. Plummer
Michael David Plummer (born 1937) is a retired mathematics professor from Vanderbilt University. His field of work is in graph theory in which he has produced over a hundred papers and publications. He has also spoken at over a hundred and fifty ...
. 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".
Fleischner's original proof was complicated.
Václav Chvátal, in the work in which he invented
graph toughness
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
, observed that the square of a ''k''-vertex-connected graph is necessarily ''k''-tough; he
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...
d that 2-tough graphs are Hamiltonian, from which another proof of Fleischner's theorem would have followed. Counterexamples to this conjecture were later discovered, 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 , was given by , and another simplified proof of the theorem was given by .
[; .]
References
Notes
Primary sources
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*. As cited by .
*.
*.
*.
*.
*.
Secondary sources
*.
*.
*{{citation
, last = Diestel , first = Reinhard
, contribution = 10. Hamiltonian cycles
, edition = corrected 4th electronic
, title = Graph Theory
, url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf
, year = 2012
Theorems in graph theory