For a connected graph, a path containing all vertices is known as a Hamiltonian path. For
general graphs, there is no known necessary and sufficient condition for the existence of
Hamiltonian paths and the complexity of finding a Hamiltonian path in general graphs is NP-
Complete. We present a necessary and sufficient condition for the existence of Hamiltonian
paths in 2-trees. Using our characterization, we also present a linear-time algorithm for the
existence of Hamiltonian paths in 2-trees. Our characterization is based on a deep …