A Proof of the Two-path Conjecture

Herbert Fleischner, Robert R. Molina, Ken W. Smith, Douglas B. West


Let $G$ be a connected graph that is the edge-disjoint union of two paths of length $n$, where $n\ge2$. Using a result of Thomason on decompositions of 4-regular graphs into pairs of Hamiltonian cycles, we prove that $G$ has a third path of length $n$.

Full Text: