# 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

### Abstract

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 language Undefined Enschede Universiteit Twente 15 0169-2690 Published - 1999

### Publication series

Name Memorandum / Faculty of Mathematical Sciences Department of Applied Mathematics, University of Twente 1499 0169-2690

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

## Cite this

Bauer, D., Broersma, H. J., Morgana, A., & Schmeichel, E. (1999). Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion. (Memorandum / Faculty of Mathematical Sciences; No. 1499). Enschede: Universiteit Twente.