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
How to Cite
Fleischner, H., Molina, R. R., Smith, K. W., & West, D. B. (2002). A Proof of the Two-path Conjecture . The Electronic Journal of Combinatorics, 9(1), #N4. https://doi.org/10.37236/1665
Issue
Volume 9 (2002)
Article Number
N4