Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion

D. Bauer, Haitze J. Broersma, A. Morgana, E. Schmeichel

Research output: Book/ReportReportProfessional

48 Downloads (Pure)


A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..
Original languageUndefined
Place of PublicationEnschede
PublisherUniversiteit Twente
Number of pages15
ISBN (Print)0169-2690
Publication statusPublished - 1999

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)0169-2690


  • MSC-05C38
  • EWI-3319
  • IR-65687
  • METIS-141297
  • MSC-68R10

Cite this