${ NP}$-complete problem "Hamiltonian cycle"\ for graph $G=(V,E)$ is extended to the "Hamiltonian Complement of the Graph"\ problem of finding the minimal cardinality set $H$ containing additional edges so that graph $G=(V,E\cup H)$ is Hamiltonian. The solving of "Hamiltonian Complement of a Graph"\ problem is reduced to the linear programming problem { \bf P}, which has an optimal integer solution. The optimal integer solution of { \bf P} is found for any its optimal solution by solving the linear assignment problem { \bf L}. The existence of polynomial algorithms for problems { \bf P} and { \bf L} proves the polynomial solvability of ${ NP}$-complete problems.
Categories: cs.CC