A Proof of the Two-path Conjecture

  • Herbert Fleischner
  • Robert R. Molina
  • Ken W. Smith
  • Douglas B. West
DOI: https://doi.org/10.37236/1665

Abstract

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$.

Published
2002-03-13
Issue
Volume 9 (2002)
Article Number
N4