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 states that, if is a 2-vertex-connected graph, then the square of is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974. An undirected graph 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. Not every 2-vertex-connected graph is Hamiltonian; counterexamples include the Petersen graph and the complete bipartite graph . The square of is a graph that has the same vertex set as , and in which two vertices are adjacent if and only if they have distance at most two in . 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 may be arranged into a cyclic order such that adjacent vertices in this order are at distance at most two from each other in . In Fleischner's theorem, it is possible to constrain the Hamiltonian cycle in so that for given vertices and of it includes two edges of incident with and one edge of incident with . Moreover, if and are adjacent in , then these are three different edges of . 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). It must also be vertex pancyclic, meaning that for every vertex and every integer k with , there exists a cycle of lengt containing . If a graph 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.