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 ${\displaystyle G}$ is a 2-vertex-connected graph, then the square of ${\displaystyle G}$ is Hamiltonian. It is named after Herbert Fleischner, who published its proof in 1974.

An undirected graph ${\displaystyle G}$ 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 ${\displaystyle K_{2,3}}$.

The square of ${\displaystyle G}$ is a graph ${\displaystyle G^{2}}$ that has the same vertex set as ${\displaystyle G}$, and in which two vertices are adjacent if and only if they have distance at most two in ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle G}$.

In Fleischner's theorem, it is possible to constrain the Hamiltonian cycle in ${\displaystyle G^{2}}$ so that for given vertices ${\displaystyle v}$ and ${\displaystyle w}$ of ${\displaystyle G}$ it includes two edges of ${\displaystyle G}$ incident with ${\displaystyle v}$ and one edge of ${\displaystyle G}$ incident with ${\displaystyle w}$. Moreover, if ${\displaystyle v}$ and ${\displaystyle w}$ are adjacent in ${\displaystyle G}$, then these are three different edges of ${\displaystyle G}$.

In addition to having a Hamiltonian cycle, the square of a 2-vertex-connected graph ${\displaystyle G}$ 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 ${\displaystyle v}$ and every integer ${\displaystyle k}$ with ${\displaystyle 3\leq k\leq |V(G)}$, there exists a cycle of length ${\displaystyle k}$ containing ${\displaystyle v}$.

If a graph ${\displaystyle 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.

An infinite graph cannot have a Hamiltonian cycle, because every cycle is finite, but Carsten Thomassen proved that if ${\displaystyle G}$ is an infinite locally finite 2-vertex-connected graph with a single end then ${\displaystyle G^{2}}$ necessarily has a doubly infinite Hamiltonian path. More generally, if ${\displaystyle G}$ is locally finite, 2-vertex-connected, and has any number of ends, then ${\displaystyle G^{2}}$ has a Hamiltonian circle. 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.

The Hamiltonian cycle in the square of an ${\displaystyle n}$-vertex 2-connected graph can be found in linear time, improving over the first algorithmic solution by Lau of running time ${\displaystyle O(n^{2})}$. Fleischner's theorem can be used to provide a 2-approximation to the bottleneck traveling salesman problem in metric spaces.