Hamiltonicity of Cartesian products of graphs

A path factor in a graph G is a factor of G in which every component is a path on at least two vertices. Let T Pₙ be the Cartesian product of a tree T and a path on n vertices. Kao and Weng proved that T Pₙ is hamiltonian if T has a path factor, n is an even integer and n≥ 4Δ (T)-2. They conjectured that for every Δ ≥ 3 there exists a graph G of maximum degree Δ which has a path factor, such that for every even n< 4Δ-2 the product G Pₙ is not hamiltonian. In this article we prove this conjecture.