@book{e587396bc3614c4291fd1d11d3a45c63,

title = "Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion",

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..",

keywords = "MSC-05C38, EWI-3319, IR-65687, METIS-141297, MSC-68R10",

author = "D. Bauer and Broersma, {Haitze J.} and A. Morgana and E. Schmeichel",

note = "Imported from MEMORANDA",

year = "1999",

language = "Undefined",

isbn = "0169-2690",

series = "Memorandum / Faculty of Mathematical Sciences",

publisher = "University of Twente",

number = "1499",

address = "Netherlands",

}